洛谷 B3644. 【模板】拓扑排序 / 家谱树
原题链接
简单
算法
(拓扑排序)
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
int main() {
int n;
cin >> n;
vector<vector<int>> to(n);
vector<int> deg(n);
rep(v, n) {
int u;
while (cin >> u, u) {
--u;
to[v].push_back(u);
deg[u]++;
}
}
queue<int> q;
rep(i, n) if (deg[i] == 0) q.push(i);
vector<int> ans;
while (q.size()) {
int v = q.front(); q.pop();
ans.push_back(v+1);
for (int u : to[v]) {
deg[u]--;
if (deg[u] == 0) {
q.push(u);
}
}
}
for (int v : ans) cout << v << ' ';
return 0;
}