题目描述
家庭关系可以用家谱树来表示,给定一个家谱树,你的任务是找出其中没有孩子的成员。
输入格式
第一行包含一个整数 N 表示树中结点总数以及一个整数 M 表示非叶子结点数。
接下来 M 行,每行的格式为:
ID K ID[1] ID[2] ... ID[K]
ID 是一个两位数字,表示一个非叶子结点编号,K 是一个整数,表示它的子结点数,接下来的 K 个 ID[i]
也是两位数字,表示一个子结点的编号。
为了简单起见,我们将根结点固定设为 01。
所有结点的编号即为 01,02,03,…,31,32,33,…,N。
输出格式
输出从根结点开始,自上到下,树的每一层级分别包含多少个叶子节点。
输出占一行,整数之间用空格隔开。
数据范围
0<N<100
输入样例:
2 1
01 1 02
输出样例:
0 1
样例解释
该样例表示一棵只有 2 个结点的树,其中 01 结点是根,而 02 结点是其唯一的子节点。
因此,在根这一层级上,存在 0 个叶结点;在下一个级别上,有 1 个叶结点。
所以,我们应该在一行中输出0 1。
示例2
Sample Input:
5 3
01 2 02 03
02 1 05
03 1 04
Sample Output:
0 0 2
算法1
考虑到是一层层的计算有无叶子结点。开始是尝试使用bfs 广度优先搜索
依照层次逐步向下搜索,搜索过程中是带上了当前节点的层级,如果发现层级数有变化,
那么就可以将上一层级的统计出叶子结点放入答案.
C++ 代码
#include <iostream>
#include <map>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 150;
map<int, vector<int>> mm;
int n, m;
vector<int> ans;
void bfs(int x) {
queue<pair<int, int>> q;
int currLevel = 1;
int currCount = 0;
q.push({ x,currLevel });
while (!q.empty()) {
int curr = q.front().first;
int level = q.front().second;
q.pop();
if (level != currLevel) {
ans.push_back(currCount);
currLevel = level;
currCount = 0;
}
if(mm[curr].size()==0) { currCount++; }
for (int i = 0; i < mm[curr].size(); i++) {
int next = mm[curr][i];
q.push({ next,level + 1 });
}
}
ans.push_back(currCount);
return;
}
int main()
{
cin >> n >> m;
for (int i = 0; i < m; i++) {
int curr; int count; int t;
cin >> curr >> count;
for (int j = 0; j < count; j++) {
cin >> t;
mm[curr].push_back(t);
}
}
if (m == 0) {
cout << 1 << endl;
return 0;
}
bfs(1);
for (int i = 0; i < ans.size(); i++) {
cout << ans[i] ;
if(i != ans.size()-1){
cout << " ";
}
}
cout << endl;
return 0;
}