记录编号	93532	评测结果	AAAAAAAAAA
题目名称	[POI 2002]滑雪者	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.049 s
提交时间	2014-03-26 21:16:09	内存使用	96.16 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int SIZEN=5010;
int N;
vector<int> c[SIZEN];
int color[SIZEN]={0};//0白1黑-1灰
int father[SIZEN]={0};
int f[SIZEN][SIZEN]={0};
int ans=0;
void DFS(int u){
	color[u]=-1;
	for(int i=0;i<c[u].size();i++){
		int v=c[u][i];
		if(color[v]==0){
			father[v]=u;
			DFS(v);
		}
		else{//来到了一个之前访问过的点,即找到了一个域
			int vl=v,vh=v;
			int nowmax=0;
			while(color[vh]==1){//黑色就是域边上的点
				nowmax=max(nowmax,f[vh][father[vh]]);//寻找左边界上的最大值
				vh=father[vh];
			}
			nowmax++;
			ans=max(ans,nowmax);
			father[v]=u;
			while(vl!=vh){//把右边界上的值都更新了
				f[vl][father[vl]]=nowmax;
				vl=father[vl];
			}
		}
	}
	color[u]=1;
}
void read(void){
	scanf("%d",&N);
	int k,t;
	for(int i=1;i<=N-1;i++){
		scanf("%d",&k);
		for(int j=1;j<=k;j++){
			scanf("%d",&t);
			c[i].push_back(t);
		}
	}
}
int main(){
	freopen("skiers.in","r",stdin);
	freopen("skiers.out","w",stdout);
	read();
	color[N]=1;//因为要计算"最左边"一溜的值
	DFS(1);
	printf("%d\n",ans);
	return 0;
}