AcWing 848. 有向图的拓扑序列
原题链接
简单
作者:
tidycoder
,
2021-03-19 12:09:43
,
所有人可见
,
阅读 284
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<int> degree(n+1, 0);
vector<vector<int>> edges(n+1, vector<int>());
int a, b;
for (int i = 0; i < m; ++i) {
cin >> a >> b;
degree[b]++;
edges[a].push_back(b);
}
queue<int> q;
for (int i = 1; i <= n; ++i) {
if (degree[i] == 0) {
q.push(i);
}
}
vector<int> ans;
while (!q.empty()) {
int v = q.front();
q.pop();
ans.push_back(v);
for (int target : edges[v]) {
degree[target]--;
if (degree[target] == 0) {
q.push(target);
}
}
}
if (ans.size() == n)
for (int i = 0; i < ans.size(); ++i) {
cout << ans[i] << " ";
}
else cout << -1;
return 0;
}