3065489_ac_125ms_2824k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int n, stone;
vector <int> graph[1001];
int mark[1001];
int visited[1001];
int que[1001];
int f, r, cnt, ans;

void bfs(int v)
{
	int i, m, num;
	int t[1001], max;

	f = r = -1;
	que[++r] = v;
	visited[v] = cnt;
	t[v] = 0;
	num = 1;
	max = 0;
	while (f!=r)
	{
		++f;
		m = que[f];
		for (i = 0; i < graph[m].size(); i++)
		{
			if (visited[graph[m][i]]!=cnt)
			{
				num++;
				visited[graph[m][i]] = cnt;
				t[graph[m][i]] = t[m]+1;
				if (t[graph[m][i]]>max)
				{
					max = t[graph[m][i]];
				}
				que[++r] = graph[m][i];
				if (num==n)
				{
					f = r;
					break;
				}
			}
		}
	}
	if (num==n)
	{
		if (max >= ans)
		{
			ans = max;
			stone = v;
		}
	}
	else
	{
		for (i = 0; i <= r; i++)
		{
			mark[que[i]] = 1;
		}
	}
}

int main()
{
	int i, j, k, t;

	scanf("%d",&n);
	for (i = 0; i < n; i++)
	{
		scanf("%d",&k);
		for (j = 0; j < k; j++)
		{
			scanf("%d",&t);
			t--;
			graph[i].push_back(t);
		}
	}
	cnt = 1;
	ans = -1;
	for (i = 0; i < n; i++)
	{
		if(mark[i]==1)
			continue;
		bfs(i);
		cnt++;
	}
	if (ans==-1)
	{
		puts("impossible");
	}
	else
	{
		printf("%d\n%d\n",ans,stone+1);
	}
	return 0;
}