拓扑排序（10/18）

拓扑排序

https://raelum.blog.csdn.net/article/details/129650604?ydreferer=aHR0cHM6Ly93d3cuYWN3aW5nLmNvbS9hY3Rpdml0eS9jb250ZW50L2NvZGUvY29udGVudC80NzEwNi8%3D

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n,m;

int h[N],ne[N],e[N],idx=0;

int q[N];int in[N];int tt=-1,hh=0;

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

bool topsort()
{
    //遍历找入度为0的点存进队列
    for(int i=1;i<=n;i++)
    {
        if(in[i]==0) q[++tt]=i;
    }
    
    while(hh<=tt)
    {
        int t=q[hh++];
        for(int i=h[t];i!=-1;i=ne[i])
        {
            //下一节点的入度减1，即砍去这条边，如果为入度0，就加入队列
            int j=e[i];
            in[j]--;
            if(in[j]==0) q[++tt]=j;
        }
    }
    return tt+1==n;//是tt不是hh,所有元素的下标
}



int main()
{
    memset(h,-1,sizeof h);
    cin>>n>>m;int x,y;
    while(m--)
    {
        scanf("%d%d",&x,&y);
        add(x,y);
        in[y]++;
    }
    
    if (!topsort()) puts("-1");
    else
    {
        for (int i = 0; i < n; i ++ ) printf("%d ", q[i]);
        puts("");
    }
    
    return 0;
}