题目描述
庭关系可以用家谱树来表示,给定一个家谱树,你的任务是找出其中没有孩子的成员。
输入格式
第一行包含一个整数 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。
算法1
(bfs) $O(n^2)$
刚开始直接莽了一个暴力bfs算法,由于bfs可以比较方便的求出每一层有哪些节点,判断每一层的节点时否是叶子节点就可以,时间复杂度我看大概是dfs的两倍(还是太菜了)
时间复杂度
参考文献
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=500+10;
int g[N][N];
queue<int>q;
int n,m;
bool vis[N];
bool check(int fa)
{
for(int i=1;i<=n;i++)
{
if(g[fa][i]==1&&fa!=i)return false;
}
return true;
}
int main()
{
cin>>n>>m;
for(int i=0;i<m;i++)
{
int id,k;
cin>>id>>k;
for(int j=1;j<=k;j++)
{
int d;
cin>>d;
g[id][d]=1;
}
}
for(int i=1;i<=n;i++)g[i][i]=1;
q.push(1);
while(!q.empty())
{
queue<int>t1;
int num=0;
while(!q.empty())
{
int x=q.front();
t1.push(x);
q.pop();
if(check(x))num++;
}
cout<<num;
while(!t1.empty())
{
int t=t1.front();
t1.pop();
for(int j=1;j<=n;j++)
{
if(g[t][j]==1&&!vis[j]&&t!=j)
{
q.push(j);
vis[j]=true;
}
}
}
if(!q.empty())cout<<" ";
}
return 0;
}
算法2
(dfs) $O(n)$
这里学到了一种新的存储图的方式vector[HTML_REMOVED]g[N]一个vector数组,本质上和临街矩阵存储图一样,但是vector毕竟有一些api可以直接调用.
这里dfs计算深度,每一个深度其实就是每一个层级,每当遇到一个没有儿子节点的点,就根据当前深度在当前深度上加一个1,表示这一层级的儿子节点。
遍历到叶子结点将对应深度处的数量加1,同时更新最大深度以便于最后的输出
此处采用邻接表存储图,v[i].size() == 0 表示无孩子即为叶节点,否则从上到下遍历所有的孩子节点,传入的深度 depth+1
时间复杂度
参考文献
https://www.acwing.com/user/myspace/index/31488/
C++ 代码
#include <iostream>
#include <vector>
using namespace std;
const int N = 110;
vector<int> v[N]; // 存储图
int d[N]; // 深度叶子个数
int maxdepth;
void dfs(int u, int depth)
{
if(!v[u].size()) // 叶子结点
{
d[depth]++;
maxdepth = max(maxdepth, depth);
return;
}
for(int i = 0; i < v[u].size(); i++)
dfs(v[u][i], depth+1);
}
int main()
{
int n, m;
scanf("%d%d", &n, &m);
while(m--)
{
int id, k, ch;
scanf("%d%d", &id, &k);
while(k--)
{
scanf("%d", &ch);
v[id].push_back(ch);
}
}
dfs(1, 0);
printf("%d", d[0]);
for(int i = 1; i <= maxdepth; i++)
printf(" %d", d[i]);
puts("");
return 0;
}