拓扑排序的判断与输出（BFS与DFS）

//拓扑排序BFS实现思路：
// 1、建立入度数组，存储每个结点的入度；
// 2、利用辅助队列，遍历入度数组，将所有入度为零的结点入队；
// 3、循环判断队列是否为空，若不空：取队首元素，更新该节点相邻节点的入度，将入度为零的结点入队；
// 4、若输出结点数与图结点数相同则该图具有拓扑序列，返回判断结果；

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

using namespace std;

const int N = 1e5, M = 1e5;
int n,m,q[N],d[N];

struct Node{
    int val;
    Node* next;
    Node(int _val): val(_val), next(NULL){};
}*head[N];

void add(int a, int b){
    Node *p = new Node(b);
    p -> next = head[a];
    head[a] = p;
}

bool topSort(){
    int t = -1, h = 0;

    for(int i = 1; i <= n; i++){
        if(d[i] == 0) q[++ t] = i;
    }

    while(h <= t){
        int u = q[h ++];

        for(Node* p = head[u]; p; p = p -> next){
            int c = p -> val;
            if(-- d[c] == 0){
                q[++ t] = c;
            }
        }
    }

    return n - 1 == t;
}

int main(){
    cin >> n >> m;
    int a,b;

    while(m--){
        cin >> a >> b;
        add(a,b);
        d[b] ++;
    }

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

    return 0;
}

拓扑排序DFS实现思路：

// 1、建立状态数组，0代表还未访问，1代表正在访问，2代表已访问过；
// 2、递归实现dfs（i），令st[i] = 1代表正在递归，遍历递归i的相邻结点；
// 3、递归遍历其相邻节点过程中，若访问到的结点状态：
//      为0:继续递归访问该点；
//      为1:访问到了正在递归的结点，说明有环，返回false
// 4、若一条路递归没有环到底，则将该结点加入数组（导致数组存储的是逆拓扑序列）
// 5、在topSort方法中对每个节点都进行递归的dfs，若均返回true则说明该图为有向无环图
// 6、在主函数中逆输出数组q，即得到拓扑序列

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

using namespace std;

const int N = 1e5, M = 1e5;
int n,m,top = 1,q[N];
int st[N];//0代表还未访问，1代表正在访问，2代表已访问

struct Node{
    int val;
    Node* next;
    Node(int _val): val(_val), next(NULL){};
}*head[N];

void add(int a, int b){
    Node *p = new Node(b);
    p -> next = head[a];
    head[a] = p;
}

bool dfs(int u){
    st[u] = 1;

    for(Node* p = head[u]; p; p = p -> next){
        int t = p -> val;
        if(st[t] == 0){
            if(!dfs(t)) return false;
        }
        else if (st[t] == 1) return false;
    }

    q[top ++] = u;//到这里说明该条路径没有环

    st[u] = 2;

    return true;
}


bool topSort(){
    for(int i = 1; i <= n; i++){
        if(!st[i] && !dfs(i)){
            return false;
        }
    }

    return true;
}

int main(){
    cin >> n >> m;
    int a,b;

    for(int i = 1; i <= m; i++){
        cin >> a >> b;
        add(a,b);
    }

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

    return 0;
}