有向图才会有拓扑序列，对于每条边，起点在终点前面

有环一定没有拓扑序

可证明有向无环图一定有拓扑图，所以有向无环图也被称为拓扑图

如何求拓扑序

度：入度和出度

所有当前入度为0的点都可以作为起点

入度为零意味着没有任何一条边指向当前点

宽搜过程

848. 有向图的拓扑序列 - AcWing题库

题目概述

给定一个有向图，包含 $n$ 个点和 $m$ 条边，可能存在重边和自环。要求输出该图的任意一个拓扑序列，如果不存在拓扑序列（即图中存在环），则输出 $-1$。

解题思路

拓扑排序是针对有向无环图（DAG）的一种线性排序方法，使得对于图中的每一条有向边 $(u, v)$，$u$ 在排序中总是位于 $v$ 的前面。如果图中存在环，则无法进行拓扑排序。

方法步骤

1. 计算入度：统计每个节点的入度（即有多少条边指向该节点）。
2. 初始化队列：将所有入度为0的节点加入队列。这些节点没有前置依赖，可以直接作为拓扑序列的起始点。
3. 处理队列：从队列中取出一个节点，将其加入拓扑序列，并移除所有从该节点出发的边（即减少其邻居节点的入度）。如果邻居节点的入度变为0，则将其加入队列。
4. 检查结果：如果拓扑序列包含所有节点，则排序成功；否则，说明图中存在环，无法进行拓扑排序。

代码解析

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = N * 2;
int h[N], e[M], ne[M], idx; // 邻接表存储图
int q[N], d[N]; // q数组模拟队列，d数组存储入度
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;

    // 将所有入度为0的节点加入队列
    for(int i = 1; i <= n; i ++) {
        if(!d[i])
            q[++ tt] = i;
    }

    while(hh <= tt) {
        int t = q[hh ++]; // 取出队头节点

        // 遍历该节点的所有邻居
        for(int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            d[j] --; // 邻居节点的入度减1
            if(d[j] == 0) // 如果入度为0，加入队列
                q[++ tt] = j;
        }
    }

    // 如果队列中的节点数等于n，说明拓扑排序成功
    return tt == n - 1;
}

int main() {
    memset(h, -1, sizeof h); // 初始化邻接表

    cin >> n >> m;
    while(m --) {
        int a, b;
        cin >> a >> b;
        d[b] ++; // 更新节点b的入度
        add(a, b); // 添加边a->b
    }

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

代码解释

1. 邻接表存储图：使用数组模拟邻接表，h数组存储每个节点的头指针，e和ne数组分别存储边的终点和下一条边的索引。
2. 入度数组d：记录每个节点的入度。
3. add函数：添加一条从a到b的边，并更新b的入度。
4. topsort函数：
5. 初始化队列，将所有入度为0的节点加入队列。
6. 处理队列中的节点，减少其邻居节点的入度，如果邻居节点入度为0则加入队列。
7. 最后检查队列中的节点数是否等于n，如果是则说明拓扑排序成功。
8. 主函数：读取输入，构建图，调用topsort函数并输出结果。

复杂度分析

• 时间复杂度：$O(n + m)$，每个节点和每条边各处理一次。
• 空间复杂度：$O(n + m)$，存储图结构和队列。

示例输入输出

输入：

3 3
1 2
2 3
1 3

输出：

1 2 3

解释：拓扑序列可以是 1 2 3 或 1 3 2，代码输出前者。

声明：

该题解由作者学习算法基础课后，ac本题，使用deepseek生成，相关图片由作者截图添加