题解 | 【模板】拓扑排序

将所有入度为0的顶点入队；

遍历队列，将顶点加入拓扑序列，并将相邻顶点入度减1，若为0，则加入队列；

若拓扑序列长度等于顶点数n，则输出序列；否则图中存在环，输出-1。

#include <iostream>
#include<vector>
#include<queue>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    vector<vector<int>>adj(n+1);
    vector<int>in_d(n+1,0);
    for(int i=0;i<m;i++){
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        in_d[v]++;
    }
    queue<int>q;
    for(int i=1;i<=n;i++){
        if(in_d[i]==0)q.push(i);
    }
    vector<int>res;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        res.push_back(u);
        for(int v:adj[u]){
            if(--in_d[v]==0)q.push(v);
        }
    }
    if(res.size()!=n)cout<<-1<<endl;
    else{
        for(int i=0;i<n;i++){
            if(i)cout<<' ';
            cout<<res[i];
        }
        cout<<endl;
    }
    return 0;
}