1004 Counting Leaves

 1 #include<iostream>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 struct node
 6 {
 7     int father,level,child;
 8 }a[110];
 9 int level[110];
10 int main()
11 {
12     ios::sync_with_stdio(false);
13     cin.tie(0);
14     cout.tie(0);
15     int n,m;
16     while(cin>>n>>m)
17     {
18         memset(a,0,sizeof(a));
19         memset(level,0,sizeof(level));
20         int id,k,child_id;
21         int max_level=1;//这里着重说明一下如果不像特别处理的话初始化为1比较好，有一个样例一直不过是因为我一开始初始化-1，后来发现如果只有一个节点的话，这个变量无法在下面更新，就会出错。
22         for(int i=0;i<m;i++)
23         {
24             cin>>id>>k;
25             a[id].child=1;//id这个节点有孩子
26             for(int j=0;j<k;j++)
27             {
28                 cin>>child_id;
29                 a[child_id].father=id;
30             }
31         }
32         a[1].level=1;//设置根节点在第一层
33         for(int i=1;i<=n;i++)
34         {
35             for(int j=1;j<=n;j++)
36             {
37                 if(a[j].father==i)
38                 {
39                     a[j].level=a[a[j].father].level+1;
40                     if(a[j].level>max_level)
41                     {
42                         max_level=a[j].level;
43                     }
44                 }
45             }
46         }
47         for(int i=1;i<=n;i++)
48         {
49             if(a[i].child==0)//统计每一层有多少个叶节点
50             {
51                 level[a[i].level]++;
52             }
53         }
54         for(int i=1;i<max_level;i++)
55         {
56             cout<<level[i]<<" ";
57         }
58         cout<<level[max_level]<<endl;
59     }
60     return 0;
61 }