1004. Counting Leaves
程序员文章站
2022-06-11 15:18:52
...
思路:该题存储时将id对应的儿子节点存储在vector中,利用深度优先搜索对每个节点进行遍历,知道找到该id下没有儿子节点,说明该结点为叶子结点,传递参数时有一个参数level,每一次执行一次DFS,说明层数加一。Counter记录某一层叶子结点的个数。
#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
#define MaxNum 101
using namespace std;
int counter[MaxNum] = {0}, M, N, id, child_id, K;
map<int, vector<int>>child;
void DFS(int id,int level) {
if (child[id].empty()) {//如果id的儿子节点为空说明其为叶子结点
counter[level]++;//则该层叶子结点数加1
return;
}
vector<int>::iterator it;
for (it = child[id].begin(); it != child[id].end(); it++) {//对所有结点进行深度遍历,找到其儿子的节点为叶子结点
DFS(*it, level + 1);
}
}
int main()
{
int leaf,Count;
cin >> N>> M;
leaf = N - M;//leaf叶子结点的个数
while (M--) {
cin >> id>>K;
while (K--) {
cin >> child_id;
child[id].push_back(child_id);//将该id下的所有儿子节点加入
}
}
DFS(1,0);
cout << counter[0];
Count = counter[0];
for (int i = 1; Count < leaf;i++) {//当Count==leaf时说明所有叶子结点已经全部输出
cout << " " << counter[i];
Count += counter[i];
}
return 0;
}
上一篇: php smarty 基础