题解 | #【模板】拓扑排序#

//找了半天错，结果是因为最后一个输出不能有空格
//非常常规的拓扑排序模板题
#include <iostream>
#include <vector>
#include <queue>
using namespace std;


int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n + 1);
    vector<int> edg(n + 1);
    for (int i = 0; i < m; i++) {
        int a, b;
        scanf("%d %d\n",&a, &b);
        g[a].push_back(b);
        edg[b]++;
    }
    vector<int> res;
    queue<int> q;
    
    for (int i = 1; i <= n; i++) {
        if (edg[i] == 0) q.push(i);
    }
    
    while (!q.empty()) {
        int t = q.front();
        q.pop();
        res.push_back(t);
        for (int k : g[t]) {
            if (--edg[k] == 0) q.push(k);
        }
    }
    if (res.size() != n) 
        printf("-1");
    else {
        for (int i = 0; i < n - 1; i++) {
            printf("%d ",res[i]);
        }
        printf("%d",res[res.size()-1]);
    }
    return 0;
}