重铸华农荣光 我辈义不容辞

The sixteenth day - topsort

我在数据结构课学的定义结构体模拟队列、存图是一坨什么沟史

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

const int N=100010;
int h[N],e[N],ne[N],idx;
int d[N],ans[N],cnt=0;
queue<int> q;
int n,m;

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
} 

int topsort()
{
    for(int i=1;i<=n;i++) if(d[i]==0) q.push(i);

    while(q.size()){
        int t=q.front();
        ans[cnt++]=t;
        q.pop();
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            d[j]--;
            if(d[j]==0) q.push(j);
        }
    }

    if(cnt!=n) return 0;
    else return 1;
}

int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
        d[b]++;
    }

    if(topsort()) for(int i=0;i<n;i++) cout<<ans[i]<<" ";
    else cout<<"-1";

    return 0;
}