p3408.cpp

大概POJ上50道比较难的题的代码

#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 1001;
bool vi[MAXN];
vector < int > d[MAXN];
int N;
int bfs(int root){
	int l[MAXN],t[MAXN];
	int fa = 0, ch = 0;
	l[0] = root;
	t[0] = 0;
	vi[root] = true;
	while(fa <= ch){
		int f(l[fa]);
		for(int i = 0;i < d[f].size();++i)
			if(!vi[d[f][i]]){
				vi[d[f][i]] = true;
				l[++ch] = d[f][i];
				t[ch] = t[fa] + 1;
			}
		++fa;
	}
	for(int i = 0;i < N;++i) if(!vi[i]) return -1;
	return t[ch];
}

int main(){
	cin >> N;
	int i;
	for(i = 0;i < N;++i){
		int n,x;
		scanf("%d",&n);
		for(int j = 0;j < n;++j){
			scanf("%d",&x);
			d[i].push_back(x-1);
		}
	}
	int ans1(-1),ans2;
	for(i = 0;i < N;++i){
		memset(vi,false,sizeof(vi));
		int t(bfs(i));
		if(t >= ans1){
			ans1 = t;
			ans2 = i + 1;
		}
	}
	if(ans1 == -1) puts("impossible");
	else printf("%d\n%d\n",ans1,ans2);
}