1004 Counting Leaves (30分)

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<vector>
 4 #include<queue> 
 5 #include<algorithm>
 6 using namespace std;
 7 int main(){  
 8           int N,M;
 9           scanf("%d%d",&N,&M);
10           
11           int Node[N+1]={0};//Node[i]表示第i个顶点的层数 
12           Node[1]=1;        //编号为1的顶点层数为1 
13           vector<vector<int> >Edge(N+1);//图的边数组 
14           
15           int id,K,child_id;
16           for(int i=0;i<M;i++){
17               scanf("%d%d",&id,&K);
18               for(int j=0;j<K;j++){
19                   scanf("%d",&child_id);
20                   Edge[id].push_back(child_id);
21               }
22           }
23     
24        queue<int> Q;
25        Q.push(1); 
26        int count=1; 
27        while(!Q.empty()){
28            int v=Q.front();
29            Q.pop();
30            for(int i=0;i<Edge[v].size();i++) {   
31                Q.push(Edge[v][i]);
32                Node[Edge[v][i]]=Node[v]+1;
33                if(count<Node[v]+1)
34                   count=Node[v]+1;
35            }
36        }
37           
38           vector<vector<int> >data(count+1);
39           for(int i=1;i<=N;i++)
40           {
41                data[Node[i]].push_back(i);
42           }
43        int result[count]={0};
44        int num;  
45           for(int i=1;i<=count;i++)
46           {
47               num=0;
48               for(int j=0;j<data[i].size();j++)
49               {
50                   if(Edge[data[i][j]].empty())
51                       num++;
52               }
53               
54               result[i-1]=num;
55               
56           }
57           for(int i=0;i<count;i++)
58           {
59               if(i==count-1)
60                 printf("%d",result[i]);
61                 else
62               printf("%d ",result[i]);
63           }
64 return 0;
65 }