AcWing 848. 有向图的拓扑序列
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
struct Node {
int nxt, to;
}nodes[N];
int vers[N], cnt;
int q[N], d[N]; //q为队列数组,d记录每个节点的入度;
int len;
int n, m;
void add(int u, int v)
{
nodes[++cnt].to = v;
nodes[cnt].nxt = vers[u];
vers[u] = cnt;
}
bool topsort()
{
int head = 0;
for (int i = 1; i <= n; ++i) {
if (d[i] == 0) {
q[len++] = i; //将入度为0的点加入队列
}
}
while (head != len) {
for (int p = vers[q[head]]; p != 0; p = nodes[p].nxt) {
int j = nodes[p].to;
--d[j]; //将这条边删除,入度减一
//如果入度已经为0,就加入队列中
if (d[j] == 0) {
q[len++] =j;
}
}
++head;
}
//因为如果无环的话,每个节点最多入队一次,队列最终入队的元素数量就等于节点数量
return len == n;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("D:/VS CODE/C++/in.txt", "r", stdin);
freopen("D:/VS CODE/C++/out.txt", "w", stdout);
#endif
cin >> n >> m;
for (int i = 0; i < m; ++i) {
int u, v;
scanf("%d %d", &u, &v);
add(u, v);
++d[v]; //增加入度
}
bool first = true;
if (topsort()) {
for (int i = 0; i < len; ++i) {
printf(first ? "%d" : " %d", q[i]);
first = false;
}
}
else {
printf("-1");
}
fclose(stdin);
fclose(stdout);
return 0;
}