bfs-拓扑序列

重点
1. 如果图中存在环，则一定有点不能入队列
2. 队列中的点的顺序就是拓扑序列
3. 拓扑序列不唯一
4. 一个点的入度为0，则可以放入队列中作为起始点

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int h[N], ne[N], e[N], cnt;
int q[N], d[N];
int n, m;

void add(int a, int b) {
    e[cnt] = b, ne[cnt] = h[a], h[a] = cnt++;
}

int topsort() {
    int hh = 0, tt = -1;
    for (int i = 1; i <= n; i++) {
        if (!d[i]) q[++tt] = i;
    }

    while (hh <= tt) {  // 队列不为空
        int t = q[hh++];
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            d[j]--;
            if (d[j] == 0) q[++tt] = j;
        }
    }
    return tt == n - 1;
}

int main() {
    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()) {
        for (int i = 0; i < n; i++) cout << q[i] << ' ';
        puts("");
    } else cout << -1 << endl;

    return 0;
}