PAT甲级1004：统计叶节点数量

1 #include
2 using namespace std;
3 const int N&＃61;1e4&＃43;5;
4 struct node
5 {
6 int level,child;//level为该节点层数&＃xff0c;child为该节点孩子数
7 node()
8 {
9 level&＃61;10000;
10 child&＃61;0;
11 }
12 }no[N];
13 int n,m;
14 int ans[N];//ans【i】为第i层叶子节点数
15 int cmp(struct node x,struct node y)
16 {
17 return x.level<y.level;
18 }
19 int main()
20 {
21 cin>>n;
22 if (n&＃61;&＃61;0)
23 return 0;
24 cin>>m;
25 no[1].level&＃61;1;
26 int k,id,child,maxlevel&＃61;1;//maxlevel为最大层数
27 for (int i&＃61;0;i)
28 {
29 cin>>id>>k;
30 no[id].child&＃61;k;
31 for (int i&＃61;0;i)
32 {
33 cin>>child;
34 no[child].level&＃61;no[id].level&＃43;1;
35 maxlevel&＃61;max(maxlevel,no[child].level);
36 }
37 }
38 sort(no&＃43;1,no&＃43;1&＃43;n,cmp);//按层数排序
39 memset(ans,0,sizeof(ans));
40 for (int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)
41 {
42 if (no[i].child&＃61;&＃61;0)
43 {
44 ans[no[i].level ]&＃43;&＃43;;
45 }
46 }
47 cout<1];
48 for (int i&＃61;2;i<&＃61;maxlevel;i&＃43;&＃43;)
49 cout<<" "<<ans[i];
50 cout<<endl;
51
52 return 0;
53 }

1 #include
2 using namespace std;
3 vector<int> ve[110];
4 int n,m,maxlevel&＃61;0;//maxleve记录树的最大层数
5 int ans[110];//ans[i]保存第i层的叶子节点数
6 void dfs(int level,int id)//level为当前层数&＃xff0c;id为当前节点编号
7 {
8 if (ve[id].size()&＃61;&＃61;0)//找到叶子节点
9 {
10 maxlevel&＃61;max(maxlevel,level);
11 ans[level]&＃43;&＃43;;
12 return;
13 }
14 for (int i&＃61;0;i//递归遍历孩子节点
15 {
16 dfs(level&＃43;1,ve[id][i]);
17 }
18 }
19 int main()
20 {
21 cin>>n;
22 if (n&＃61;&＃61;0)
23 return 0;
24 cin>>m;
25 int id,k,child;
26 for (int i&＃61;0;i)
27 {
28 cin>>id>>k;
29 for (int j&＃61;0;j)
30 {
31 cin>>child;
32 ve[id].push_back(child);
33 }
34 }
35 memset(ans,0,sizeof(ans));
36 dfs(0,1);
37 cout<0];
38 for (int i&＃61;1;i<&＃61;maxlevel;i&＃43;&＃43;)
39 {
40 cout<<" "<<ans[i];
41 }
42 cout<<endl;
43
44 return 0;
45 }