A28828. 家谱树
填空题
困难
知识点
题目描述
家谱树
题目描述
有个人的家族很大，辈分关系很混乱，请你帮整理一下这种关系。
给出每个人的孩子的信息。
输出一个序列，使得每个人的后辈都比那个人后列出。
输入
第1行一个整数N（1≤N≤100），表示家族的人数；
接下来N行，第i行描述第i个人的儿子；
每行最后是0表示描述完毕。
输出
输出一个序列，使得每个人的后辈都比那个人后列出；
如果有多解输出任意一解。
输入样例
5
0
4 5 1 0
1 0
5 3 0
3 0输出样例
2 4 5 3 1参考答案
#include<bits/stdc++.h>
using namespace std;
#define N 105
vector<int> edge[N];
int n, deg[N];//deg[i]:顶点i的入度
void init()//建图
{
int f, t;
cin >> n;
for(f = 1; f <= n; ++f)
{
while(cin >> t && t != 0)
{
edge[f].push_back(t);
deg[t]++;
}
}
}
void topoSort()//拓扑排序
{
queue<int> que;
for(int i = 1; i <= n; ++i)
if(deg[i] == 0)
{
cout << i << ' ';
que.push(i);
}
while(que.empty() == false)
{
int u = que.front();
que.pop();
for(int v : edge[u])
{
deg[v]--;
if(deg[v] == 0)
{
cout << v << ' ';
que.push(v);
}
}
}
}
int main()
{
init();
topoSort();
return 0;
}
上一题
下一题