记录编号	38392	评测结果	AAAAAAAAAA
题目名称	[USACO Open09] 捉迷藏	最终得分	100
用户昵称	TBK	是否通过	通过
代码语言	C++	运行时间	0.203 s
提交时间	2012-04-18 12:31:33	内存使用	5.02 MiB

#include <iostream> 
#include <cstdio> 
#include <cstdlib> 
#include <cmath> 
#include <cstring> 
#include <string> 
#include <iomanip> 
#include <vector> 
#include <set> 
#include <algorithm> 
#define MAXN 0x7fffffff 
using namespace std; 
int a,b,c,d,l,m,n,r[20001],h=1,t,x[1000000],k[20001];
bool bo[20001];
struct fun
{
	int x;
	int y;
}f[100001];
int Compare(const void*elem1,const void*elem2)
{
	struct fun*elem3=(struct fun*)elem1;
	struct fun*elem4=(struct fun*)elem2;
	if (elem3->x != elem4->x) return elem3->x - elem4->x;
		else return elem3->y - elem4->y;
}
void BFS(void)
{
	bo[1]=true;
	while (h>t)
	{
		for (l=k[x[t]-1];l<k[x[t]];l++)
			if (bo[f[l].y]==false)
			{
				bo[f[l].y]=true;
				r[f[l].y]=r[x[t]]+1;
				x[h]=f[l].y;
				h++;
			}
		t++;
	}
}
int main(void) 
{ 
    freopen("hideseek.in","r",stdin); 
    freopen("hideseek.out","w",stdout); 
    scanf("%d%d",&b,&c);
	for (d=0;d<c;d++)
	{
		scanf("%d%d",&f[d].x,&f[d].y);
		f[d+c].x=f[d].y;
		f[d+c].y=f[d].x;
	}
	c*=2;
	qsort(f,c,sizeof(fun),Compare);
	k[0]=0;
	k[b]=c;
	for (d=0;d<c-1;d++)
		if (f[d].x!=f[d+1].x) k[f[d].x]=d+1;
	for (d=1;d<b-1;d++)
		if (k[d]==0) k[d]=k[d-1];
	x[0]=1;
	BFS();
	for (d=1;d<=b;d++)
		if (r[d]>n) 
		{
			n=r[d];
			m=1;
			l=d;
		}
			else if (r[d]==n) m++;
	printf("%d %d %d",l,r[l],m);
    fclose(stdin); 
    fclose(stdout); 
    return 0; 
}