数组模拟队列拓扑排序

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

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

void ins(int x, int y){
    e[idx]=y;
    ne[idx]=h[x];
    h[x]=idx++;
}

bool topSort(){
    int HEAD=0;
    int TAIL=-1;
    // 将入度为0的元素加入到队列中
    for(int i=1; i<=n; ++i){
        if(!d[i]) q[++TAIL]=i;
    }
    while(HEAD<=TAIL){
        int t=q[HEAD++];
        for(int i=h[t]; i!=-1; i=ne[i]){
            int j=e[i];
            d[j]--;
            if(d[j]==0) q[++TAIL]=j;
        }
    }
    return TAIL==n-1;
}


int main(){
    cin>>n>>m;
    memset(h, -1, sizeof h);
    memset(d, 0x00, sizeof d);
    // build graph
    int x, y;
    while(m--){
        cin>>x>>y;
        ins(x, y);
        d[y]++;
    }

    if(topSort()){
        for(int i=0; i<n; ++i) cout<<q[i]<<" ";
        cout<<endl;
    }
    else cout<<"-1"<<endl;

    return 0;
}

queue容器

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

const int N=1e5+5;
vector<int> G[N];
vector<int> res; // 存储拓扑序列
int DEG[N];
int n, m;


// 拓扑排序(bfs)
bool topSort(){
    queue<int> q;
    for(int i=1; i<=n; ++i)
        if(!DEG[i])
            q.push(i);

    while(!q.empty()){
        int node=q.front();
        res.push_back(node);
        q.pop();
        for(auto &e: G[node]){
            --DEG[e];
            if(!DEG[e]) q.push(e);
        }
    }
    return res.size()==n;
}


int main(){
    memset(DEG, 0x00, sizeof DEG);
    cin>>n>>m;
    int x, y;
    while(m--){
        cin>>x>>y;
        G[x].push_back(y);
        DEG[y]++;
    }

    if(topSort()){
        for(auto &e: res) cout<<e<<" ";
        cout<<endl;
    }
    else cout<<"-1"<<endl;
    return 0;
}