基于BFS的拓扑排序

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

using namespace std;

const int N = 100010;

// 基于BFS的图的拓扑排序-数组模拟队列(为了能保存拓扑排序的结果)

// n-图的点数 m-图的边数
int n,m;

// q[hh]-队头元素,q[tt]-队尾元素,d[id]-编号为id的顶点的入度
int q[N],d[N];

// 邻接表存储图-顶点表head[id]和边表Node分别存储顶点id和与id连接的所有边
struct Node {
    int id;
    Node* next;
    Node(int _id):id(_id),next(NULL) {} // 构造函数方便初始化
} *head[N];

// 添加有向边a->b 实际上就是往a的边表里加入顶点b
void add(int a,int b) {
    auto p = new Node(b);
    p->next = head[a];
    head[a] = p;
}

bool topsort() {
    // hh指向队头元素,tt指向队尾元素
    int hh = 0,tt = -1;
    // 1. 找到入度为0的顶点 入队
    for(int i = 1;i <= n;i ++) {
        if(!d[i]) q[++ tt] = i;
    }

    // 当队列非空
    while(hh <= tt) {
        // 取出队头
        int t = q[hh ++];
        // 2. 将与该顶点相邻的所有边都删除-即入度-1
        for(auto p = head[t];p;p = p->next) {
            d[p->id] --;
            // 3. 入度为0的顶点继续入队 直到所有顶点都入队表示成功
            if(!d[p->id]) q[++ tt] = p->id;
        }
    }
    return tt == n - 1;
}

int main()
{
    cin >> n >> m;

    while(m --) {
        int a,b;
        cin >> a >> b;
        add(a,b);
        // 每添加a->b这么一条边,就会对b增加一个入度
        d[b] ++;
    }

    // 有向无环图一定有拓扑排序,有环图一定没有拓扑排序
    if(!topsort()) puts("-1");
    else {
        for(int i = 0;i < n;i ++)
            printf("%d ",q[i]);
    }
    return 0;
}

基于dfs的拓扑排序-记BFS版本拓扑排序即可,这个太难了

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

using namespace std;

const int N = 100010, M = 100010;

int n, m;
struct Node
{
    int id;
    Node* next;
    Node(int _id): id(_id), next(NULL) {}
}*head[N];
int st[N], q[N], top;

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

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

    for (auto p = head[u]; p; p = p->next)
    {
        int j = p->id;
        if (!st[j])
        {
            if (!dfs(j)) return false;
        }
        else if (st[j] == 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()
{
    scanf("%d%d", &n, &m);
    while (m -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
    }

    if (!topsort()) puts("-1");
    else
    {
        for (int i = n - 1; i >= 0; i -- )
            printf("%d ", q[i]);
    }

    return 0;
}