欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

1004. Counting Leaves

程序员文章站 2022-06-11 15:18:52
...

1004. Counting Leaves

思路:该题存储时将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;
}