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

#include <bits/stdc++.h>
using namespace std;

const int MAX=2e5+10;
int in[MAX];
vector<int>tu[MAX];

queue<int>a;
int n,m;
int b[MAX];
void tuopu()
{
    for(int i=1;i<=n;i++)
        if(in[i]==0)
            a.push(i);
    int count=0;
    while(!a.empty())
    {
        int c=a.front();
        a.pop();
        b[count]=c;
        count++;
        for(int i=0;i<tu[c].size();i++)
        {
            int t=tu[c][i];
            in[t]--;
            if(in[t]==0)
                a.push(t);
        }
    }
    if(count==n)
    {
        for(int w=0;w<n;w++)
        {   
            if(w!=0)
                cout<<" ";//容易在结尾多打一个空格
            cout<<b[w];
        }
        return;
    }
    else
        cout<<"-1";
    return;
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        tu[x].push_back(y);
        in[y]++;
    }
    tuopu();
    return 0;
}