1094. The Largest Generation (25)时间限制200 ms内存限制65536 kB代码长度限制16000 B判题程序Standard作者CHEN, YueA family hierarchy is usually presented by a pedigree tree where all the nodes on the same level belong to the same generation. Your task is to find the generation with the largest population.Input Specification:Each input file contains one test case. Each case starts with two positive integers N (<100) which is the total number of family members in the tree (and hence assume that all the members are numbered from 01 to N), and M (<N) which is the number of family members who have children. Then M lines follow, each contains the information of a family member in the following format:ID K ID[1] ID[2] … ID[K]where ID is a two-digit number representing a family member, K (>0) is the number of his/her children, followed by a sequence of two-digit ID’s of his/her children. For the sake of simplicity, let us fix the root ID to be 01. All the numbers in a line are separated by a space.Output Specification:For each test case, print in one line the largest population number and the level of the corresponding generation. It is assumed that such a generation is unique, and the root level is defined to be 1.Sample Input:23 1321 1 2301 4 03 02 04 0503 3 06 07 0806 2 12 1313 1 2108 2 15 1602 2 09 1011 2 19 2017 1 2205 1 1107 1 1409 1 1710 1 18Sample Output:
9 4
//有同学用并查集也可以过的
//六度空间
#include<iostream>#include<cstring>#include<string>#include<cmath>#include<map>#include<queue>#include<cstdio>#include<vector>#include<algorithm>using namespace std;const int maxn=105;const int inf=210000;vector<int> g[maxn];bool vis[maxn];int lev=1;int sum;int ans=1;//ans=0的话第二个样例过不去，能找到这个错误，我也是醉了void bfs(int s){queue<int> q;q.push(s);vis[s]=true;int tail;int last=s;int cnt=1;while(!q.empty()){int k=q.front();q.pop();int n=g[k].size();for(int i=0;i<n;i++){if(!vis[g[k][i]]){q.push(g[k][i]);vis[g[k][i]]=true;tail=g[k][i];sum++;}}if(k==last){last=tail;cnt++;if(ans<sum){ans=sum;lev=cnt;}sum=0;}}}int main(){int n,m,i,j,k,t;freopen("in.txt","r",stdin);scanf("%d%d",&n,&m);for(i=0;i<m;i++){int id;cin>>id>>k;for(j=0;j<k;j++){cin>>t;g[id].push_back(t);g[t].push_back(id);}}bfs(1);printf("%d %d\n",ans,lev);return 0;}
，才能做到人在旅途，感悟人生，享受人生。
