题解 | 【模板】拓扑排序

#include<bits/stdc++.h>

using namespace std;

const int N=2e5+5;

int n,m;
int b[N];
int vis[N];
int bel[N];
int cnt;

vector<int>V[N];

queue<int>q;

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        V[u].push_back(v);
        b[v]++;
    }
    for(int i=1;i<=n;i++) 
        if(b[i]==0) 
        {
            q.push(i);
            vis[i]=++cnt;
            bel[cnt]=i;
        }
    while(!q.empty())
    {
        int tmp=q.front();
        q.pop();
        for(int i=0;i<V[tmp].size();i++)
        {
            b[V[tmp][i]]--;
            if(!b[V[tmp][i]])
            {
                vis[V[tmp][i]]=++cnt;
                bel[cnt]=V[tmp][i];
                q.push(V[tmp][i]);
            }
        }
    }
    if(cnt<n) cout<<-1;
    else
    {
        for(int i=1;i<=cnt;i++)
        {
            cout<<bel[i];
            if(i<cnt) cout<<' ';
        }
    }
    return 0;
}