题目必须01节点为根节点，测试点才过，
如果将输入的第一个节点的level初始化为1，则不通过。
要看清题目啊！！——固定根为01
题目大意
n个节点， m个父节点
根节点固定为01
给出每个父节点的所有儿子，找出每层节点的叶子数目。
处理
1.数组处理
采用顺序存储结构，数组存储每节点，
每节点记录是否为父节点， 其父节点， 所处层数。
#include<bits/stdc++.h>
#define MAXN 110
using namespace std
;
typedef struct node
{
int father
, level
, flag
;
}node
;
int main(){
node nodes
[MAXN
];
int n
, m
, ID
, k
;
int result
[MAXN
] = {0};
int maxlevel
= 1;
cin
>> n
>> m
;
for(int i
= 0; i
<= n
; i
++){
nodes
[i
].father
= nodes
[i
].level
= nodes
[i
].flag
= 0;
}
nodes
[1].level
= 1;
for(int i
= 0; i
< m
; i
++){
cin
>> ID
>> k
;
if(k
)
nodes
[ID
].flag
= 1;
int child
;
for(int j
= 1; j
<= k
; j
++){
cin
>> child
;
nodes
[child
].father
= ID
;
}
}
for(int i
= 1; i
<= n
; i
++){
if(nodes
[i
].flag
){
for(int j
= 1; j
<= n
; j
++){
if(nodes
[j
].father
== i
){
nodes
[j
].level
= nodes
[i
].level
+ 1;
}
}
}
}
for(int i
= 1; i
<= n
; i
++){
if(!nodes
[i
].flag
&& nodes
[i
].level
> 0){
result
[nodes
[i
].level
]++;
}maxlevel
= (maxlevel
< nodes
[i
].level
)?nodes
[i
].level
:maxlevel
;
}
for(int i
= 1; i
< maxlevel
; i
++){
cout
<< result
[i
] << " ";
}
cout
<< result
[maxlevel
];
return 0;
}
2.dfs(), 遍历计算每层叶子数目
vector， map的使用！
#include<bits/stdc++.h>
#define MAXN 110
using namespace std
;
vector
<int> tree
[MAXN
];
map
<int, int > level
;
int n
, m
;
void dfs(int node
, int lev
);
int main(){
int ID
, k
;
cin
>> n
>> m
;
for(int i
= 0; i
< m
; i
++){
cin
>> ID
>> k
;
int child
;
for(int j
= 0; j
< k
; j
++){
cin
>> child
;
tree
[ID
].push_back(child
);
}
}
if(m
== 0){cout
<< n
<< endl
; return 0;}
dfs(1, 1);
int i
;
cout
<< level
[1];
for(i
= 2; i
<= level
.size(); i
++){
cout
<< " " << level
[i
];
}
return 0;
}
void dfs(int node
, int lev
){
if(tree
[node
].size() == 0){
level
[lev
]++;
return;
}
else{
for(int i
= 0; i
< tree
[node
].size(); i
++){
dfs(tree
[node
][i
], lev
+1);
}
}
return;
}
