AcWing 1191. 家谱树
原题链接
简单
作者:
fakesmile
,
2020-07-03 14:19:47
,
所有人可见
,
阅读 464
#include <iostream>
#include <queue>
#include <list>
#include <algorithm>
#include <vector>
using namespace std;
int n;
vector<list<int>> adj;
vector<int> indgree;
queue<int> q;
vector<int> res;
void topsort()
{
for(int i = 1; i <= n; i++)
{
if(!indgree[i])
q.push(i);
}
while(!q.empty())
{
int t = q.front();
q.pop();
for(auto iter = adj[t].begin(); iter != adj[t].end(); iter++)
{
indgree[*iter]--;
if(!indgree[*iter])
q.push(*iter);
}
res.push_back(t);
}
}
int main()
{
scanf("%d", &n);
adj = vector<list<int>>(n + 1, list<int>());
indgree = vector<int>(n + 1, 0);
//读入拓扑图
for(int i = 1; i <= n; i++)
{
int x;
while(cin >> x && x)
{
adj[i].push_back(x);
indgree[x]++;
}
}
topsort();
for(int i = 0; i < n; i++)
{
printf("%d ", res[i]);
}
return 0;
}