AcWing 848. 有向图的拓扑序列
原题链接
简单
作者:
piaofan
,
2021-02-22 16:38:25
,
所有人可见
,
阅读 191
#include<bits/stdc++.h>
using namespace std;
const int N = 100005;
int e[N], ne[N], h[N], idx;
int n, m, d[N];
queue<int> q, q1;
void add (int a, int b) {
e[idx] = b, ne[idx] = h[a]; h[a] = idx++;
}
bool topsort () {
for (int i = 1; i <= n; i++) {
if (!d[i]) q.push(i);
}
while (!q.empty()) {
int t = q.front(); q.pop(); q1.push(t);
for (int i = h[t]; i != -1; i = ne[i]) {
int j = e[i];
if (--d[j] == 0) q.push(j);
}
}
int s = q1.size();
return s == n;
}
int main (void) {
cin >> n >> m;
memset(h, -1, sizeof(h));
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
add(a, b); d[b]++;
}
if (!topsort()) puts("-1");
else {
while (!q1.empty()) {
int t = q1.front();
cout << t << " ";
q1.pop();
}
}
}