题解 | 【模板】拓扑排序

拓扑排序板子，如果是刚接触图论的话这个主要是用来判环，还是比较好用和好写的。原理是不断删去入度为0的点，这样环外的点会不断从叶子脱落(离环最远的点姑且称作叶子)，而环上的点会被天然地保留下来。具体实现是使用队列存储还未删去的入度为0的节点。初始时遍历每个节点判断入度是否为0，若为叶子则入队。初始化结束后不断地取队首进行删去操作，并将新成为叶子的节点加入队列即可，具体来说就是将与当前要删去节点所指向的所有节点的入度都减1，若减完后某个节点入度为0则意味着成为了新的叶子，入队。重复这个过程，删去节点的同时将该节点加入结果序列，可以实现有向无环图的拓扑排序。

#include<bits/stdc++.h>
using namespace std;
int n, m, u, v, deg[200005];
vector<int> g[200005];
int main() {
    cin>>n>>m;
    for(int i=1; i<=m; i++) {
        cin>>u>>v;
        g[u].push_back(v);
        deg[v]++;
    }
    queue<int> q;
    vector<int> ans;
    for(int i=1; i<=n; i++) {
        if(!deg[i]) {
            q.push(i);
            ans.push_back(i);
        }
    }
    while(!q.empty()) {
        int u=q.front(); q.pop();
        for(auto &v: g[u]) {
            deg[v]--;
            if(!deg[v]) {
                q.push(v);
                ans.push_back(v);
            }
        }
    }
    if(ans.size()<n) cout<<-1;
    else {
        int f=0;
        for(auto &ele: ans) {
            if(f) cout<<' ';
            cout<<ele;
            f=1;
        }
    }
}