拓扑排序

一、 拓扑排序的核心概念

1. 定义

拓扑排序是**针对有向无环图（DAG, Directed Acyclic Graph）**的一种特殊排序方式，它将图中所有节点排成一个线性序列，满足：对于图中的任意一条有向边 u→v，在该线性序列中，节点 u 一定出现在节点 v 之前。

关键补充（信奥赛高频考点）

1. 拓扑排序的前提条件：图必须是有向无环图（DAG），有环的图不存在拓扑排序（比如之前的序列排序问题中，A<B、B<C、C<A 形成环，直接判定矛盾）。
2. 拓扑排序的结果不唯一（除非每一步选择入度为0的节点唯一）。例如图 A→C、B→C，拓扑序列可以是 A→B→C，也可以是 B→A→C（之前的序列排序问题中，正是利用“每一步入度为0的节点唯一”来判定序列是否确定）。
3. 节点的入度：指向该节点的有向边数量；节点的出度：该节点指向其他节点的有向边数量（拓扑排序的核心依赖入度判断）。

2. 核心作用

结合之前的题目，拓扑排序在信奥赛中的核心应用场景有以下4类，覆盖90%以上的相关考题：

1. 判断有向图是否存在环（最基础应用）
   • 原理：执行拓扑排序后，若得到的节点数量小于图中总节点数量，说明存在环（无法完成全部节点的排序）。
   • 对应题目：序列排序问题（判断矛盾，即是否存在环）。
2. 求解DAG的最长路径/最短路径（高频应用）
   • 原理：拓扑排序保证了节点的线性顺序，对于任意边 u→v，u 一定先于 v 被处理，因此可以在遍历拓扑序列时，逐步更新 v 的最长/最短路径值。
   • 对应题目：DAG中1到n的最长路径（无法用Dijkstra，拓扑排序是最优解）、序列排序问题中判断最长路径是否等于节点数（确定序列唯一性）。
3. 确定依赖关系的执行顺序
   • 原理：现实中的依赖问题（如课程先修、任务调度）可转化为DAG，拓扑排序给出合法的执行顺序。
   • 对应题目：奶牛聚餐（寻找所有奶牛可达的牧场，本质是依赖可达性的拓扑扩展）、序列排序（确定元素的大小关系顺序）。
4. 统计可达性/交集问题
   • 原理：基于拓扑排序的遍历（BFS/DFS），可以高效统计单个节点的可达节点集合，进而求解多节点可达集合的交集。
   • 对应题目：奶牛聚餐（统计每头奶牛的可达牧场，求交集）。

二、 拓扑排序的两种核心模板代码（信奥赛应试首选）

拓扑排序的实现有两种方式：Kahn算法（BFS实现，首选）和DFS回溯实现，其中Kahn算法更直观、易调试、便于扩展（如统计路径长度），是信奥赛中的主流选择，下面给出两种模板的精简实现（适配C++11，可直接拷贝应试）。

模板1： Kahn算法（BFS实现，核心推荐）

算法思路

1. 统计所有节点的入度，存入入度数组 in[]。
2. 初始化队列，将所有入度为0的节点加入队列。
3. 循环处理队列：
   • 取出队首节点 u，加入拓扑序列。
   • 遍历 u 的所有邻接节点 v，将 v 的入度减1（相当于删除 u→v 这条边）。
   • 若 v 的入度变为0，将 v 加入队列。
4. 最终，若拓扑序列的长度等于节点总数，说明无环，排序成功；否则存在环，排序失败。

精简模板代码

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

const int N = 1505; // 可根据题目调整（如26、1005、1505）
vector<int> g[N]; // 邻接表，存储有向边（u→v）
int in[N]; // 入度数组
int n, m; // n：节点数，m：边数

// 返回值：pair<是否无环, 拓扑序列>
pair<bool, vector<int>> topo_sort_kahn() {
    vector<int> topo_seq; // 存储拓扑序列
    queue<int> q; // BFS队列，存储入度为0的节点

    // 1. 初始化队列：将所有入度为0的节点入队
    for (int i = 1; i <= n; ++i) { // 节点编号根据题目调整（0~n-1 或 1~n）
        if (in[i] == 0) {
            q.push(i);
        }
    }

    // 2. 处理队列，生成拓扑序列
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        topo_seq.push_back(u); // 加入拓扑序列

        // 遍历u的所有邻接节点，更新入度
        for (int v : g[u]) {
            if (--in[v] == 0) {
                q.push(v);
            }
        }
    }

    // 3. 判断是否有环（拓扑序列长度是否等于节点总数）
    bool is_dag = (topo_seq.size() == n);
    return {is_dag, topo_seq};
}

// 主函数调用示例（适配题目输入格式）
int main() {
    cin >> n >> m;
    memset(in, 0, sizeof(in)); // 初始化入度数组为0

    // 构建邻接表 + 统计入度
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        in[v]++; // 有向边u→v，v的入度+1
    }

    // 执行Kahn算法
    auto [is_dag, topo_seq] = topo_sort_kahn(); // 若编译器不支持C++17，改用pair的first/second

    // 结果处理（根据题目需求修改）
    if (!is_dag) {
        cout << "存在环，无拓扑序列" << endl;
    } else {
        cout << "拓扑序列：";
        for (int x : topo_seq) {
            cout << x << " ";
        }
        cout << endl;
    }

    return 0;
}

模板2： DFS回溯实现（补充，应对特殊场景）

算法思路

1. 维护一个访问标记数组，标记节点的状态：未访问、正在访问（当前递归栈中）、已访问。
2. 对每个未访问的节点执行DFS：
   • 标记节点为“正在访问”。
   • 遍历该节点的所有邻接节点，若邻接节点未访问，则递归访问；若邻接节点“正在访问”，说明存在环。
   • 递归回溯后，标记节点为“已访问”，并将节点加入拓扑序列（逆序）。
3. 最终反转拓扑序列，得到合法的拓扑序列（若无环）。

精简模板代码（适配信奥赛）

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

const int N = 1505;
vector<int> g[N];
int vis[N]; // 0：未访问，1：正在访问，2：已访问
vector<int> topo_seq;
int n, m;
bool has_cycle = false; // 是否存在环

void dfs(int u) {
    if (has_cycle) return;
    vis[u] = 1; // 标记为正在访问（递归栈中）

    for (int v : g[u]) {
        if (vis[v] == 0) {
            dfs(v);
        } else if (vis[v] == 1) {
            // 找到环，标记并返回
            has_cycle = true;
            return;
        }
    }

    vis[u] = 2; // 标记为已访问
    topo_seq.push_back(u); // 回溯时加入序列（逆序）
}

// 执行DFS版拓扑排序
pair<bool, vector<int>> topo_sort_dfs() {
    has_cycle = false;
    topo_seq.clear();
    memset(vis, 0, sizeof(vis));

    for (int i = 1; i <= n; ++i) {
        if (vis[i] == 0 && !has_cycle) {
            dfs(i);
        }
    }

    if (has_cycle) {
        return {false, {}};
    }

    reverse(topo_seq.begin(), topo_seq.end()); // 反转得到正确拓扑序列
    return {true, topo_seq};
}

// 主函数调用示例（同Kahn算法）
int main() {
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
    }

    auto [is_dag, seq] = topo_sort_dfs();
    if (!is_dag) {
        cout << "存在环，无拓扑序列" << endl;
    } else {
        cout << "拓扑序列：";
        for (int x : seq) {
            cout << x << " ";
        }
        cout << endl;
    }

    return 0;
}

三、 拓扑排序的注意事项

1. 图的节点编号问题（最易出错）
   • 题目中节点编号可能是 0~n-1（如字母A~Z对应0~25），也可能是 1~n（如牧场、图的顶点），入度数组、邻接表的索引必须与节点编号对应。
   • 示例：序列排序问题中，字母A对应0，B对应1，此时循环应从0到n-1，而非1到n。
2. 入度数组的初始化与拷贝
   • 多轮拓扑排序（如序列排序问题，每输入一个关系执行一次拓扑排序）时，不能修改原始入度数组，应使用临时入度数组（tmp_in），通过memcpy或循环拷贝原始入度。
   • 错误示例：直接修改原始入度数组，导致后续轮次的拓扑排序入度数据异常。
3. 重复边的处理
   • 题目中可能出现重复的有向边（如序列排序问题中的重复关系A<B），重复边会导致入度重复累加，应使用二维数组edge[u][v]标记边是否已存在，避免重复加边。
4. 拓扑序列唯一性的判断（高频考点）
   • 若题目要求判断拓扑序列是否唯一（如序列排序问题），在Kahn算法中，每一步队列中入度为0的节点数量必须为1，若某一步队列大小>1，说明序列不唯一。
5. 数据类型与溢出问题
   • 求解DAG最长路径/最短路径时，路径权值可能累加（边权范围±1e5，节点数≤1500），应使用long long类型存储路径值，避免int类型溢出。
6. 无解的判断条件
   • 存在环：拓扑序列长度<节点总数。
   • 无法到达：如DAG中1到n的最长路径，若最终dp[n]为负无穷（初始值），说明无法到达。
7. BFS与DFS的选择
   • 优先选择Kahn算法（BFS实现）：直观、易调试、便于扩展（如统计路径长度、判断序列唯一性），且避免DFS的递归栈溢出问题（节点数较多时，递归深度过大可能栈溢出）。
   • DFS实现仅在特殊场景下使用（如题目要求递归实现，或需要额外记录节点访问状态）。

四、 总结（信奥赛应试核心提炼）

1. 核心前提：拓扑排序仅适用于有向无环图（DAG），有环图无拓扑序列。
2. 核心实现：首选Kahn算法（BFS），记住“统计入度→入度为0节点入队→处理节点更新入度”的三步流程。
3. 核心应用：判断环、求解DAG最长/最短路径、确定依赖顺序、统计可达性，这四类场景覆盖了所有拓扑排序相关考题。
4. 避坑关键：节点编号对应、入度数组拷贝、重复边处理、序列唯一性判断、数据类型溢出，这五点是减少应试失误的核心。
5. 模板化应试：将Kahn算法模板熟记于心，根据题目需求修改节点编号、结果处理逻辑，即可快速应对绝大多数拓扑排序考题。