拓扑排序（acwing）

//输入一个图 判断是否为拓扑排序（没有环）

/* 3 3
   1 2
   2 3
   1 3
   */          //样例输出为1  2  3
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int N=10010;
int h[N],e[N],ne[N],idx=0;
int d[N],n,m,q[N];
void add(int a,int b)
{
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
void topsort()
{
    int tt=0;      //    最后输出 q[tt]
    queue<int>que;
    for(int i=1;i<n;i++)
    if(d[i]==0)             //说明没有路指向他 他可以看成是起点
        que.push(i);
    while(!que.empty())
    {
        int t=que.front();
        q[tt++]=t;             //将每个起点存到q[]中 作为最后输出
        que.pop();
        for(int i=h[t];i!=-1;i=ne[i])
        {
            d[e[i]]--;            //遍历到他 指向他的路就减一 
            if(d[e[i]]==0)          //变成0时 就是他成为新的起点（没有点再指向他）
                que.push(e[i]);   //将新的起点入列        }  
    }
    if(tt==n)                  //说明所有点最终都成为 0 点 ，说明是一条单向路 没有环
        for(int i=0;i<tt;i++)
            cout<<q[i]<<' ';
    else
        cout<<"-1";
    cout<<endl;
    return ;
}


int main(void)
{
    cin>>n>>m;
    memset(h,-1,sizeof(h));
    memset(d,0,sizeof(d));          //d[]存有多少条路指向他
    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
        d[b]++;          //指向b的路加一
    }
    topsort();
    return 0;
}