STL实现的拓扑排序（多开一个seq数组记录排序后的结果）

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

const int N=1e5+10;
int h[N],e[N],ne[N],idx;
int d[N],seq[N];
int n,m;

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

bool  topsort(){
    queue<int> q;

    //把入度为0的点放入队列
    for(int i=1;i<=n;i++){
        if(!d[i]) q.push(i);
    }

    //遍历当前点能到的所有点，能到的入度都减去1 
    int k=0;
    while(!q.empty()){
        int t=q.front();
        q.pop();
        seq[k++]=t;

        for(int i=h[t];i!=-1;i=ne[i]){
            int j=e[i];
            if(--d[j]==0){
                q.push(j);
            }
        }
    }
    return k==n;
}

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<<seq[i]<<' ';
        cout<<endl;
    }else{
        cout<<"-1"<<endl;
    }
}

数组模拟链表实现

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=2*N;

int h[N],e[M],ne[M],idx;
int q[N],d[N];
int n,m;


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]) q[++tt]=i;    //将入度为0的点加入队列
    }

     while (hh <= tt)
    {
        int t = q[hh ++ ];

        for (int i = h[t]; i!= -1; i = ne[i])
        {
            int j = e[i];
            if (-- d[j] == 0)
                q[ ++ tt] = j;
        }
    }

    return tt == n - 1;

    while(hh<=tt){
        int t=q[hh++];
        for(int i=h[t];i!=-1;i=ne[i]){
            int j=e[i];
            if(--d[j]==0){
                q[++tt]=j;
            }
        }
    }
    return tt==n-1;   //所有n个点都进了队列，该图是有向无环图
}

int main(){
    cin>>n>>m;
    memset(h,-1,sizeof(h));
    while(m--){
        int a,b;
        cin>>a>>b;
        add(a,b);
        d[b]++;   //入度+1
    }
    if(topsort()){
        for(int i=0;i<n;i++) cout<<q[i]<<' ';
        cout<<endl;
    }else{
        cout<<"-1"<<endl;
    }
}