c++ DFS求拓扑序

#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
#include <vector>

using namespace std;
const int N=105;
const int M=N*N/2;

int head[N], E=0;
int vis[N];
struct Edge{int v, ne;}e[M];
void add(int a, int b){
    e[E].v=b;
    e[E].ne=head[a];
    head[a]=E++;
}

int n;
queue<int> q;
vector<int> ans;

bool dfs(int u){
    vis[u]=1; // 当前u在系统栈中
    for(int i=head[u]; ~i; i=e[i].ne){
        int v=e[i].v;
        if(vis[v]==1) return false; // 存在环
        else if(!vis[v] && !dfs(v)) return false;
    }
    vis[u]=-1; // 已经访问
    ans.insert(ans.begin(), u);
    return true;
}

int main(){
    memset(head, -1, sizeof head);
    memset(vis, 0x00, sizeof vis);
    cin>>n;
    for(int i=1; i<=n; ++i){
        int j;
        while(cin>>j, j){
            add(i, j);
        }
    }
    for(int i=1; i<=n; ++i){
        if(!vis[i] && !dfs(i)) return -1;
    }
    for(auto &e: ans) cout<<e<<" ";

    return 0;
}

c++ BFS求拓扑序

#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
#include <vector>

using namespace std;
const int N=105;
const int M=N*N/2;

int head[N], E=0;
int din[N];
struct Edge{int v, ne;}e[M];
void add(int a, int b){
    e[E].v=b;
    e[E].ne=head[a];
    head[a]=E++;
}

int n;
queue<int> q;
vector<int> ans;

void bfs(){
    while(!q.empty()){
        int node=q.front(); q.pop();
        ans.push_back(node);
        for(int i=head[node]; ~i; i=e[i].ne){
            int v=e[i].v;
            din[v]--;
            if(!din[v]) q.push(v);
        }
    }
}

int main(){
    memset(head, -1, sizeof head);
    memset(din, 0x00, sizeof din);
    cin>>n;
    for(int i=1; i<=n; ++i){
        int j;
        while(cin>>j, j){
            add(i, j);
            din[j]++;
        }
    }
    for(int i=1; i<=n; ++i){
        if(!din[i]) q.push(i);
    }

    bfs();
    for(auto &e: ans) cout<<e<<" ";

    return 0;
}