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

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int maxn=1e5+100;
int ne[maxn],e[maxn],h[maxn],idx,q[maxn],d[maxn];
void add(int a,int b)
{
    e[idx]=b; ne[idx]=h[a]; h[a]=idx++;
}
bool topsort()
{

    int hh=0,tt=-1;
    for(int i=1;i<=n;i++){
        if(d[i]==0) {
            q[++tt]=i;
        }
    }
    while(hh<=tt)
    {
        auto t=q[hh++];
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            d[j]--;
            if(d[j]==0)
            {
                q[++tt]=j;
            }
        }
    }
    return tt==n-1; //所有点的入列了，那么说明它是一个有向无环图，具有拓扑序
}
int main()
{
    memset(h,-1,sizeof h);
    int i,j,a,b;
    cin>>n>>m;
    for(i=0;i<m;i++){
        cin>>a>>b;
        add(a,b);
        d[b]++;
    }
    if(topsort())
    {
        for(i=0;i<n;i++){
            cout<<q[i]<<" ";

        }
        cn;
    }
    else
    {
        cout<<-1<<endl;
    }
    return 0;
}