拓扑排序

一、拓扑排序：概念与直觉

在我们正式定义拓扑排序之前，不妨先来看一个生活中的例子。假设你早上起床后，需要完成一系列事情才能出门：穿袜子、穿裤子、穿鞋子、穿上衣、打领带、穿外套。这些事情的顺序并不是完全随意的。例如：

• 必须先穿袜子，才能穿鞋子。
• 必须先穿上衣，才能打领带。
• 必须先穿上衣，才能穿外套。
• 必须先穿裤子，才能穿外套（通常情况下）。

我们可以将这些事情看作图中的“节点”，而这些先后顺序关系看作图中的“有向边”。例如，“穿袜子”指向“穿鞋子”的边，表示“穿袜子”是“穿鞋子”的先决条件。

这样一个由任务和它们之间的依赖关系构成的图，如果画出来，你会发现它是一个有向图 (Directed Graph)。更进一步，这个图中不应该存在“环路”。比如，你不可能要求“先穿鞋子再穿袜子，同时又要求先穿袜子再穿鞋子”，这就形成了一个逻辑上的死循环。这种没有环路有向图，我们称之为有向无环图 (Directed Acyclic Graph, 简称 DAG)。

**拓扑排序 (Topological Sort)**，正是对一个有向无环图的所有顶点进行线性排序，使得对于图中任意一条有向边 （从顶点 指向顶点 ），顶点 在这个线性序列中都出现在顶点 之前。

简单来说，拓扑排序就是给DAG中的所有节点排一个队，让所有“箭头”都指向队伍的后方。这个队列就代表了一个可行的事件发生顺序或任务执行流程。

需要注意的是：

1. 只有有向无环图（DAG）才能进行拓扑排序。如果一个有向图包含环，那么环上的顶点之间互相依赖，无法确定一个满足所有依赖关系的线性序列。
2. 一个DAG的拓扑排序结果可能不是唯一的。比如，如果任务A和任务B没有任何依赖关系，那么它们在拓扑序列中的先后顺序可以是任意的，只要它们都满足各自的先决条件即可。

在算法竞赛中，识别出问题模型中的DAG结构，并利用拓扑排序来处理节点间的依赖关系，是解决一类问题的关键。这类问题可能直接要求输出一个拓扑序列，也可能是在拓扑序的基础上进行动态规划、路径查找等操作。

二、有向无环图 (DAG) 的判定与性质

在深入拓扑排序算法之前，我们有必要简单回顾一下有向无环图。

一个有向图 由顶点集合 和有向边集合 组成。每条边 是一个有序对 ，表示从顶点 到顶点 的一条有向连接。

一个路径 (path) 是一个顶点序列 ，使得对于所有的 ， 都是图中的一条边。路径的长度是其包含的边的数量，即 。

一个环 (cycle) 是一条路径 ，其中 且路径长度 （即至少包含一条边，且起点和终点相同）。对于简单图（没有自环和平行边），通常要求环中所有中间顶点 互不相同，并且与 不同。

有向无环图 (DAG) 就是一个不包含任何环的有向图。

DAG具有一些重要的性质，这些性质与拓扑排序密切相关：

1. 存在性定理：一个有向图存在拓扑排序的充分必要条件是它是一个DAG。

   • 必要性：如果图 有一个拓扑排序，假设存在一个环 。根据拓扑排序的定义，在序列中 必须在 之前， 必须在 之前，…， 必须在 之前。这导出了一个矛盾： 必须在 之前。因此，有拓扑排序的图必为DAG。
   • 充分性：（我们将在后续算法中证明）任何DAG至少有一个入度为0的顶点，也至少有一个出度为0的顶点（除非是空图）。我们可以利用这个性质来构造拓扑排序。

2. 入度与出度：

   • 顶点的**入度 (in-degree)**，记作 ，是指向顶点 的边的数量。
   • 顶点的**出度 (out-degree)**，记作 ，是从顶点 出发的边的数量。
   • 在一个DAG中，至少存在一个入度为0的顶点。如果所有顶点的入度都大于0，那么从任意顶点出发，沿着边反向走，由于顶点有限，必然会重复访问某个顶点，从而形成一个环，这与DAG的定义矛盾。同理，DAG中也至少存在一个出度为0的顶点。

理解这些基本概念和性质，是我们学习和应用拓扑排序算法的基础。接下来，我们将介绍两种最常用的拓扑排序算法。

三、Kahn 算法 (基于BFS的拓扑排序)

Kahn 算法是一种直观且常用的拓扑排序算法，它基于广度优先搜索 (BFS) 的思想。其核心思路是：

1. 首先，找到所有入度为0的顶点，将它们加入一个队列（或集合）中。这些顶点没有任何先决条件，可以作为拓扑序列的起始部分。
2. 当队列不为空时，从中取出一个顶点 （比如队首元素）。将 加入到当前的拓扑序列中。
3. 然后，考察所有从 出发的边 。对于每个这样的邻接点 ，我们将边 从图中“移除”（逻辑上移除，实际操作是减少 的入度）。
4. 如果顶点 的入度在减少后变为0，说明 的所有先决条件都已满足，此时将 加入队列。
5. 重复步骤2-4，直到队列为空。

如果算法结束后，加入到拓扑序列中的顶点数量等于图中的总顶点数，那么这个序列就是一个合法的拓扑排序。反之，如果数量小于总顶点数，说明图中存在环，无法进行拓扑排序。这是因为环中的顶点入度永远不可能变为0（除非环中所有顶点同时被处理，但这在Kahn算法的逐个处理机制下不会发生）。

算法步骤详解

设图 ，顶点数为 ，边数为 。

1. 初始化：
   • 计算所有顶点的初始入度 。
   • 创建一个空队列 。
   • 创建一个空列表 用于存放拓扑排序的结果。
2. 找到起始顶点：
   • 遍历所有顶点 ，如果 ，则将 加入队列 。
3. 主循环：
   • 当 不为空时：
     a. 从 中取出一个顶点 (例如，u = Q.front(); Q.pop();)。
     b. 将 添加到列表 的末尾。
     c. 对于从 出发的每一条边 （即 的每一个邻接点 ）：
     i. 将 的入度减1: 。
     ii. 如果 ，则将 加入队列 。
4. 结果判断：
   • 如果列表 中包含的顶点数量等于 ，则 就是一个合法的拓扑序列。
   • 否则（数量小于 ），图中存在环，无法进行拓扑排序。

代码实现 (C++14)

我们将使用邻接表来存储图。

// 题意概括: 给定一个N个点M条边的有向图，输出其拓扑排序序列。
// 如果不存在拓扑排序（即图中有环），则报告错误。

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int MAXN = 100005; // 最大顶点数
vector<int> adj[MAXN];   // 邻接表存储图
int idg[MAXN];           // 存储每个顶点的入度
int n, m;                // n为顶点数, m为边数
vector<int> res;         // 存储拓朴排序结果

bool kahn() {
    queue<int> q;
    for (int i = 1; i <= n; ++i) { // 假设顶点编号从1到n
        if (idg[i] == 0) {
            q.push(i);
        }
    }

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        res.push_back(u);

        for (int v : adj[u]) {
            idg[v]--;
            if (idg[v] == 0) {
                q.push(v);
            }
        }
    }

    return res.size() == n; // 如果结果包含所有顶点，则成功
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v; // 一条从u到v的有向边
        adj[u].push_back(v);
        idg[v]++;      // v的入度增加
    }

    if (kahn()) {
        for (int i = 0; i < n; ++i) {
            cout << res[i] << (i == n - 1 ? "" : " ");
        }
        cout << endl;
    } else {
        cout << "Graph has a cycle!" << endl; // 或按题目要求输出特定错误信息
    }

    return 0;
}

// 时间复杂度:
// 1. 计算所有顶点的初始入度: 遍历所有边，O(M)。如果只给顶点数和邻接表，则遍历邻接表O(N+M)。
//    在此代码中，输入边时直接计算，所以是O(M)。
// 2. 将所有入度为0的顶点入队: 遍历所有顶点，O(N)。
// 3. 主循环:
//    - 每个顶点最多入队一次、出队一次，O(N)。
//    - 每条边最多被访问一次（当其起点的顶点出队时），O(M)。
// 因此，Kahn算法的总时间复杂度为 O(N + M)。
// 空间复杂度:
// - 邻接表: O(N + M)
// - 入度数组 idg: O(N)
// - 队列 q: 最多存储N个顶点，O(N)
// - 结果列表 res: 存储N个顶点，O(N)
// 总空间复杂度为 O(N + M)。

Kahn 算法的特性与讨论

1. 字典序最小的拓扑序列：
   如果题目要求输出字典序最小的拓扑序列，Kahn算法有一个天然的优势。在将入度为0的顶点加入队列时，如果使用的是优先队列 (min-priority queue) 而不是普通队列，并且优先队列以顶点编号为优先级，那么每次从优先队列中取出的就是当前所有可选顶点中编号最小的那个。这样得到的拓扑序列就是字典序最小的。
   当然，使用普通队列时，如果邻接表中的边预先按目标节点编号排序，且初始入队时也按编号排序，则在某些情况下也能得到字典序最小的，但这不具有普适性。最稳妥的方法是使用优先队列。

2. 环的检测：
   Kahn算法能非常自然地检测出图中是否存在环。如前所述，如果最终得到的拓扑序列长度小于图的总顶点数 ，则说明图中存在环。这是因为环上的顶点，它们的入度在它们的前驱节点没有被移除（即加入拓扑序列）之前，永远不会变为0。由于环的存在，导致环上的所有节点都无法入队，最终使得 res.size() 小于 n。

3. 直观性：
   Kahn算法的过程非常符合我们对“完成任务”的直观理解：先完成那些没有前置条件的任务，然后它们完成后，再去看哪些新的任务的前置条件已经满足了，如此往复。

四、DFS 算法 (基于深度优先搜索的拓扑排序)

除了Kahn算法，我们还可以使用深度优先搜索 (DFS) 来实现拓扑排序。其核心思想是：对于一个DAG，一个顶点的所有后继（它能通过一条或多条边到达的顶点）都必须在拓扑序列中排在它的后面。DFS在访问完一个顶点 的所有后代（即完成对 的所有邻接点的递归调用）之后，将 加入到一个列表的头部。最终，这个列表的顺序就是图的一个拓扑排序结果（注意，是加入头部，或者加入尾部然后反转列表）。

为什么这样做是可行的呢？考虑DFS的性质。当我们完成对一个顶点 的DFS访问（即 dfs(u) 函数即将返回时），意味着所有从 出发能到达的顶点（ 的后代）都已经完成了它们的DFS访问。如果我们将此时的 记录下来，那么所有 的后代都会在我们记录 之前被记录。如果我们将记录的顺序反转，那么 就会出现在其所有后代之前，这恰好符合拓扑排序的定义。

算法步骤详解

1. 状态标记：为了实现DFS并检测环，我们需要为每个顶点维护一个状态：

   • vis[u] = 0：顶点 尚未被访问 (unvisited)。
   • vis[u] = 1：顶点 正在被访问 (visiting)，即 已经进入DFS递归栈，但其所有邻接点尚未完全处理完毕。
   • vis[u] = 2：顶点 已经被访问完毕 (visited)，即 的所有邻接点及其后代都已处理完毕，DFS调用 dfs(u) 已经返回。

2. DFS过程 (dfs(u))：
   a. 将顶点 的状态标记为 vis[u] = 1 (visiting)。
   b. 遍历 的每一个邻接点 ：
   i. 如果 vis[v] == 0 (unvisited)，则递归调用 dfs(v)。如果在递归调用中检测到环，则立即返回（或标记存在环）。
   ii. 如果 vis[v] == 1 (visiting)，说明找到了一条从当前路径上的顶点 指向其祖先节点 (或者 自身，如果 还在递归栈中) 的边，这意味着图中存在一个环。此时，算法可以停止并报告有环。
   iii.如果 vis[v] == 2 (visited)，说明 及其后代已经处理完毕，并且 已经被加入（或将要加入）拓扑序列的某个位置。对于当前 来说，这条边 不会引入新的问题，直接跳过。
   c. 当 的所有邻接点都处理完毕后（或者 没有邻接点），将 的状态标记为 vis[u] = 2 (visited)。
   d. 将 加入到一个列表 的头部。

3. 主过程：

   • 初始化所有顶点的状态为 vis[u] = 0。
   • 创建一个空列表 。
   • 遍历所有顶点 (从1到 )：如果 vis[i] == 0，则调用 dfs(i)。如果在任何 dfs 调用中检测到环，则整个图无法进行拓扑排序。
   • 如果整个过程没有检测到环，列表 (从头到尾的顺序) 就是一个合法的拓扑序列。

代码实现 (C++14)

// 题意概括: 给定一个N个点M条边的有向图，输出其拓扑排序序列。
// 如果不存在拓扑排序（即图中有环），则报告错误。
// 使用DFS实现。

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int MAXN = 100005; // 最大顶点数
vector<int> adj[MAXN];   // 邻接表存储图
int vis[MAXN];           // 0: unvisited, 1: visiting, 2: visited
int n, m;                // n为顶点数, m为边数
vector<int> res;         // 存储拓朴排序结果 (最终会反转)
bool has_cycle = false;  // 标记是否存在环

void dfs(int u) {
    vis[u] = 1; // 标记为正在访问

    for (int v : adj[u]) {
        if (vis[v] == 0) { // 如果邻接点未访问
            dfs(v);
            if (has_cycle) return; // 如果在子调用中发现环，则立即返回
        } else if (vis[v] == 1) { // 如果邻接点正在访问，说明找到环
            has_cycle = true;
            return;
        }
        // 如果 vis[v] == 2，说明v已访问完毕，是合法的DAG边，跳过
    }

    vis[u] = 2; // 标记为已访问完毕
    res.push_back(u); // 将u加入结果列表的末尾
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v; // 一条从u到v的有向边
        adj[u].push_back(v);
    }

    for (int i = 1; i <= n; ++i) { // 假设顶点编号从1到n
        if (vis[i] == 0) { // 如果顶点未访问
            dfs(i);
            if (has_cycle) break; // 如果已检测到环，停止遍历
        }
    }

    if (has_cycle) {
        cout << "Graph has a cycle!" << endl;
    } else {
        reverse(res.begin(), res.end()); // 反转结果列表得到拓扑序
        for (int i = 0; i < n; ++i) {
            cout << res[i] << (i == n - 1 ? "" : " ");
        }
        cout << endl;
    }

    return 0;
}

// 时间复杂度:
// - DFS会访问每个顶点一次，每条边一次（在邻接表表示下）。所以DFS本身是 O(N + M)。
// - 主过程中的循环遍历所有顶点确保所有连通分量都被访问。
// 因此，总时间复杂度为 O(N + M)。
// 空间复杂度:
// - 邻接表: O(N + M)
// - vis数组: O(N)
// - 结果列表 res: O(N)
// - DFS递归栈: 最坏情况下（链状图），深度可达N，所以是 O(N)。
// 总空间复杂度为 O(N + M)。

DFS 算法的特性与讨论

1. 环的检测：
   DFS通过检查是否存在指向当前递归栈中顶点（状态为 visiting）的边（即“后向边”或“返祖边”）来检测环。一旦发现这样的边，就可以确定图中存在环。

2. 结果的顺序：
   DFS得到的拓扑序，其具体顺序取决于遍历顶点及其邻接点的顺序。它不像Kahn算法那样容易直接产生字典序最小的序列（除非对邻接表进行特殊排序并小心控制DFS的起始顺序，但这通常更复杂）。

3. 与Kahn算法的比较：

   • 实现复杂度：两者实现复杂度相近。Kahn算法是迭代的，DFS是递归的（也可以写成迭代形式，但通常递归更自然）。
   • 空间开销：DFS需要额外的递归栈空间，最坏情况下可达 。Kahn算法的队列空间也是 。主要空间都由邻接表占据。
   • 字典序：Kahn算法配合优先队列可以方便地得到字典序最小的拓扑序列。DFS算法要实现这一点相对困难。
   • 应用场景：
     • 如果只需要一个拓扑序列或判断是否有环，两者皆可。
     • 如果需要字典序最小的拓扑序列，Kahn+优先队列更优。
     • 在某些基于拓扑序的动态规划问题中，DFS的“后序遍历”特性（即一个节点在其所有后代处理完毕后才处理）有时能更自然地与DP状态转移结合。

在实际竞赛中，选择哪种算法往往取决于个人偏好以及题目的具体要求。掌握两种方法能让你在不同场景下有更多选择。

五、拓扑排序的应用与扩展

拓扑排序本身解决的是“顺序”问题，但在竞赛中，它往往不是孤立存在的，而是作为解决更复杂问题的中间步骤或核心思想。

1. 依赖性任务调度

这是拓扑排序最直接的应用。题目通常会描述一系列任务和它们之间的依赖关系（任务A必须在任务B之前完成），要求给出一个可行的执行顺序，或者判断是否存在这样的顺序。

• 例题场景：课程选修（某些课程有先修课程要求）、软件编译（模块依赖）、工序安排等。
• 解题思路：将任务视为顶点，依赖关系视为有向边。如果A是B的先决条件，则建立一条从A到B的边 。然后对此图进行拓扑排序。如果能成功排序，则输出序列；否则说明存在循环依赖，无法完成。

2. DAG上的动态规划

许多动态规划问题可以建模在DAG上。如果状态之间的转移关系形成一个DAG，那么我们就可以利用拓扑排序来确定DP的计算顺序。通常，DP的状态 表示到达顶点 或从顶点 出发的某种最优值（如最长路径、最短路径、方案数等）。

• 状态转移方向：

  • 如果 的计算依赖于其所有前驱节点（指向 的节点），那么可以按照拓扑排序的顺序进行DP。当计算 时，其所有前驱节点 （边 存在）的 值都已计算完毕。
  • 如果 的计算依赖于其所有后继节点（从 指出的节点），那么可以按照拓扑排序的逆序进行DP。当计算 时，其所有后继节点 （边 存在）的 值都已计算完毕。DFS实现的拓扑排序在将节点加入结果列表时（加入头部或最后反转），实际上是按完成时间逆序排列，这天然适合第二种DP。

• 常见问题：

  • DAG上的最长路径/最短路径：这是经典应用。设 为从某个（或所有）起点到顶点 的最长/最短路径长度。

    • 初始化：对于起点 ， (或路径上的初始权值)，其他 (最长路) 或 (最短路)。对于Kahn算法，可以将所有入度为0的节点作为起点进行初始化。
    • 转移：按拓扑序处理顶点 。对于 的每个邻接点 ，用 更新 ：
      
      
    • 这种方法比 Bellman-Ford (对一般图) 或 Dijkstra (非负权边) 在DAG上更高效，时间复杂度为 。

  • DAG上的路径计数：设 为从起点到顶点 的不同路径数量。

    • 初始化：起点 ，。其他 。
    • 转移：按拓扑序处理顶点 。对于 的每个邻接点 ：
      

• 代码示例：DAG上的最长路径 (Kahn算法实现)

// 题意概括: 给定一个N个点M条边的带权有向无环图 (DAG)，
// 边权可能为负。求从指定起点 S 到各点的最长路径。
// 如果某个点不可达，则其最长路径视为负无穷。

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int MAXN = 100005;
const ll INF = 1e18; // 代表正无穷，负无穷则为 -INF

struct Edge {
    int to;
    int w;
};
vector<Edge> adj[MAXN];
int idg[MAXN];
ll dp[MAXN]; // dp[i] 表示从起点到 i 的最长路径长度
int n, m, s; // 顶点数, 边数, 起点

void solve() {
    for (int i = 1; i <= n; ++i) {
        dp[i] = -INF; // 初始化最长路径为负无穷
    }
    dp[s] = 0; // 起点到自身的路径长度为0

    vector<int> topo; // 存储拓扑序列
    queue<int> q_kahn; 

    int cur_idg[MAXN]; // 临时入度数组供Kahn算法使用
    for(int i=1; i<=n; ++i) cur_idg[i] = idg[i];

    for (int i = 1; i <= n; ++i) {
        if (cur_idg[i] == 0) {
            q_kahn.push(i);
        }
    }

    while (!q_kahn.empty()) {
        int u = q_kahn.front();
        q_kahn.pop();
        topo.push_back(u);

        for (const auto& edge : adj[u]) {
            int v = edge.to;
            cur_idg[v]--;
            if (cur_idg[v] == 0) {
                q_kahn.push(v);
            }
        }
    }
    
    // 按拓扑序进行DP
    for (int u : topo) {
        if (dp[u] == -INF && u != s) continue; // 如果u本身从S不可达，则跳过 (除非u是S)
                                         // 对于S，dp[s]已初始化为0
        
        // 若u是起点s且s有入边，但dp[s]已设为0，则从s开始的路径是正确的
        // 若u不是s但dp[u]==-INF，说明从s到u不可达

        for (const auto& edge : adj[u]) {
            int v = edge.to;
            int w_val = edge.w; // weight
            if (dp[u] != -INF && dp[v] < dp[u] + w_val) { // 只有当u可达时才更新v
                dp[v] = dp[u] + w_val;
            }
        }
    }

    // 输出结果
    for (int i = 1; i <= n; ++i) {
        if (dp[i] == -INF) {
            cout << "INF_NEG "; 
        } else {
            cout << dp[i] << " ";
        }
    }
    cout << endl;
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m >> s; 
    for (int i = 0; i < m; ++i) {
        int u_node, v_node, w_val; // u, v, weight
        cin >> u_node >> v_node >> w_val;
        adj[u_node].push_back({v_node, w_val});
        idg[v_node]++;
    }

    solve();

    return 0;
}
// 时间复杂度:
// 1. Kahn算法获取拓扑序列: O(N + M)
// 2. 按拓扑序列进行DP: 每个顶点访问一次，每条边访问一次，O(N + M)
// 总时间复杂度: O(N + M)
// 空间复杂度: O(N + M)

3. 字典序最小/最大的拓扑序列

• 字典序最小：
  使用Kahn算法，并将普通队列换成最小优先队列 (min-priority queue)。每次从优先队列中取出编号最小的、入度为0的顶点。
  时间复杂度：。

• 字典序最大：
  类似地，使用Kahn算法，并将普通队列换成最大优先队列 (max-priority queue)。
  时间复杂度：。

4. 判断唯一拓扑序列

一个DAG的拓扑序列是唯一的，当且仅当在Kahn算法的任何一步，当从队列（或优先队列）中取出一个顶点后，队列中最多只有一个入度变为0的新顶点可以加入队列，并且初始时队列中也只有一个入度为0的顶点。
更准确地说：在Kahn算法的执行过程中，任何时刻队列中的元素个数都不超过1。如果在某一步，队列空了但还有节点未处理，则有环；如果队列大小一度超过1，则序列不唯一。

// 题意概括: 判断给定DAG的拓扑序列是否唯一。
// N个点M条边。

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int MAXN = 100005;
vector<int> adj[MAXN];
int idg[MAXN]; // 使用临时入度数组，原idg可能在其他地方用
int n_nodes, m_edges; // N, M

bool is_uniq_topo() {
    queue<int> q_bfs;
    vector<int> tmp_idg(n_nodes + 1);
    for(int i=1; i<=n_nodes; ++i) tmp_idg[i] = idg[i];

    for (int i = 1; i <= n_nodes; ++i) {
        if (tmp_idg[i] == 0) {
            q_bfs.push(i);
        }
    }

    int proc_cnt = 0; // processed_nodes_count
    while (!q_bfs.empty()) {
        if (q_bfs.size() > 1) { // 在选择下一个节点时，如果队列中不止一个，则不唯一
            return false;
        }
        int u = q_bfs.front();
        q_bfs.pop();
        proc_cnt++;

        for (int v : adj[u]) {
            tmp_idg[v]--;
            if (tmp_idg[v] == 0) {
                q_bfs.push(v);
            }
        }
    }
    // 如果proc_cnt < n_nodes, 说明有环，这种情况下唯一性无从谈起或定义为不唯一
    return proc_cnt == n_nodes; 
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n_nodes >> m_edges;
    for (int i = 0; i < m_edges; ++i) {
        int u_node, v_node;
        cin >> u_node >> v_node;
        adj[u_node].push_back(v_node);
        idg[v_node]++;
    }

    // 先用标准Kahn判断是否有环并得到一个拓扑序，如果无环再判断唯一性
    // 这里简化为is_uniq_topo函数内部proc_cnt == n_nodes隐式判断了是否有环
    if (is_uniq_topo()) { 
        // 确保is_uniq_topo能正确处理有环的情况，即proc_cnt < n_nodes时返回false
        // 如果题目保证是DAG，则返回false即意味着不唯一。
        // 严格来说，应先判环。若有环，则无拓扑序，更谈不上唯一。
        // 此处假设若proc_cnt < n_nodes，is_uniq_topo视作不唯一（或应报错有环）
        // 实际上，若proc_cnt < n_nodes，则表示有环，自然不是唯一“完整”拓扑序。
        // 多数情况下，问唯一性时已默认图是DAG。
        
        // 检查是否有环，如果用上面的is_uniq_topo，它隐含了环的检查
        // 如果proc_cnt != n_nodes，说明有环，则不唯一。
        // 重新进行一次无唯一性检查的Kahn来确定是否有环：
        queue<int> test_q;
        vector<int> test_idg(n_nodes + 1);
        for(int i=1; i<=n_nodes; ++i) test_idg[i] = idg[i];
        for(int i=1; i<=n_nodes; ++i) if(test_idg[i]==0) test_q.push(i);
        int test_cnt = 0;
        while(!test_q.empty()){
            int u = test_q.front(); test_q.pop(); test_cnt++;
            for(int v : adj[u]) {
                test_idg[v]--;
                if(test_idg[v]==0) test_q.push(v);
            }
        }

        if(test_cnt != n_nodes) {
            cout << "Graph has a cycle!" << endl;
        } else { // 是DAG
            if (is_uniq_topo()) { // 再次调用判断唯一性，确保idg没被修改
                 cout << "Unique" << endl;
            } else {
                 cout << "Not Unique" << endl;
            }
        }

    } else { 
      // is_uniq_topo 返回false，可能是因为不唯一，也可能是因为有环
      // 上面的分离逻辑更清晰
      cout << "Not Unique or Cyclic" << endl; // 笼统输出
    }


    return 0;
}
// 时间复杂度: O(N+M) for Kahn's.
// 空间复杂度: O(N+M).

注：上述 is_uniq_topo 的 main 函数中的判断逻辑可以进一步精炼。核心是先确定是DAG，再判断唯一性。

5. 与强连通分量 (SCC) 结合

有时，问题中的图可能不是DAG，而是包含环的一般有向图。我们可以先求出图的强连通分量 (SCC)，将每个SCC缩成一个点，得到的新图（商图）必然是一个DAG。然后，我们可以在这个缩点图上进行拓扑排序或相关的DAG算法。

6. 综合应用：逐步判断序列与矛盾 (P1347 排序)洛谷

P1347 排序

题目描述

一个不同的值的升序排序数列指的是一个从左到右元素依次增大的序列，例如，一个有序的数列 表示 。在这道题中，我们将给你一系列形如 的关系，并要求你判断是否能够根据这些关系确定这个数列的顺序。

输入格式

第一行有两个正整数 ， 表示需要排序的元素数量，，第 到 个元素将用大写的 表示。 表示将给出的形如 的关系的数量。

接下来有 行，每行有 个字符，分别为一个大写字母，一个 < 符号，一个大写字母，表示两个元素之间的关系。

输出格式

若根据前 个关系即可确定这 个元素的顺序 yyy..y（如 ABC），输出

Sorted sequence determined after xxx relations: yyy...y.

若根据前 个关系即发现存在矛盾（如 ），输出

Inconsistency found after x relations.

若根据这 个关系无法确定这 个元素的顺序，输出

Sorted sequence cannot be determined.

（提示：确定 个元素的顺序后即可结束程序，可以不用考虑确定顺序之后出现矛盾的情况）

题意分析:
题目要求我们处理一系列形如 的关系，每加入一个关系后，判断当前已有的关系是否足以：

1. 确定全部 个元素的一个唯一升序排列。
2. 或者发现这些关系存在矛盾（例如 且 ，形成环）。
3. 如果以上两者都不是，则继续处理下一个关系。
   如果所有关系处理完仍未满足1或2，则输出无法确定。

解题思路:
这道题的核心在于动态地（每增加一个关系后）对当前的依赖图进行拓扑排序分析。

1. 图的构建：元素（A, B, …）作为图的顶点。关系 对应一条从 到 的有向边。
2. 迭代处理：对于第 个关系：
   • 将当前关系加入图中。
   • 对包含前 个关系构成的图，尝试进行拓扑排序。
3. 状态判断：
   • 矛盾（环）：如果在拓扑排序过程中，发现图中有环（例如，Kahn算法结束后，加入拓扑序列的顶点数小于 ），则输出矛盾信息，并带上当前的 值。
   • 顺序确定：如果图无环，且能得到一个包含所有 个顶点的拓扑序列，并且这个序列是唯一的，则输出顺序确定信息，并带上 值和该序列。
   • 无法确定：如果图无环，能得到 个顶点的拓扑序列，但序列不唯一；或者图无环，但当前关系不足以连接所有 个节点形成一个完整序列（这种情况在此题设定下，若无环且节点数不足N，也归为无法确定，因为题目要的是N个元素的顺序）。
4. 唯一性判断：使用Kahn算法。在算法的每一步，如果当前入度为0的顶点队列大小超过1，则表明此时有多个顶点可以作为拓扑序列的下一个元素，因此最终序列不唯一。这个检查包括初始时入度为0的顶点集，以及每次移除一个顶点后新产生的入度为0的顶点集。

代码实现细节:

• 字母 ‘A’ 到 ‘A’+N-1 映射到整数 到 。
• 一个主循环遍历 。在循环内部，构建或更新图，并调用一个函数 get_status(k_cur) 来执行拓扑排序并返回当前状态。
• get_status 函数内部实现Kahn算法：
  • 计算入度。
  • 使用队列处理入度为0的顶点。
  • 维护一个 is_uniq 标志，在队列大小超过1时设为 false。
  • 记录拓扑排序得到的顶点数 nodes_cnt。
  • 如果 nodes_cnt < N，返回“矛盾”。
  • 如果 nodes_cnt == N 且 is_uniq 为 true，返回“顺序确定”及序列。
  • 否则，返回“无法确定”。

// 题意概括: P1347 排序。根据给定的N个元素和M个形如A<B的关系，
// 逐步判断何时能确定唯一排序或发现矛盾。

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

// 全局存储所有关系，ru[i] < rv[i]
char ru[601], rv[601]; 
int n, m; // N个元素, M个关系 (沿用题目变量名习惯n,m)

// 邻接表和入度数组，每次调用get_status时基于当前k个关系重新构建
vector<int> adj[26]; // 最多26个字母
int idg[26];         // in-degree

// 函数：获取当前k_cur个关系下的状态
// 返回: pair<int, string>
//   int: 0-无法确定, 1-顺序确定, 2-矛盾
//   string: 如果顺序确定，则为该序列
pair<int, string> get_status(int k_cur) {
    // 初始化图结构
    for(int i=0; i<n; ++i) {
        adj[i].clear();
        idg[i] = 0;
    }

    // 构建基于前k_cur个关系的图
    for (int i = 0; i < k_cur; ++i) {
        int u_idx = ru[i] - 'A'; 
        int v_idx = rv[i] - 'A'; 
        adj[u_idx].push_back(v_idx);
        idg[v_idx]++;
    }

    queue<int> q_bfs; // Kahn算法的队列
    for (int i = 0; i < n; ++i) {
        if (idg[i] == 0) {
            q_bfs.push(i);
        }
    }

    string res = "";   // 存储拓扑序列
    bool is_uniq = true; // 标记序列是否唯一
    int cnt = 0;       // 计入拓扑序列的节点数

    // Kahn算法主循环
    // 循环的目标是处理n个节点，或者队列变空（说明有环或处理完毕）
    while(cnt < n && !q_bfs.empty()){ 
        if(q_bfs.size() > 1){ // 如果在选择下一个节点时有多个选项
            is_uniq = false;  // 则最终序列不唯一
        }
        
        int u_val = q_bfs.front();
        q_bfs.pop();
        res += (char)('A' + u_val);
        cnt++;

        // 为了使is_uniq判断更稳定，以及如果唯一时输出固定（字典序），
        // 将新变为0入度的节点排序后入队。
        vector<int> next_q_add; 
        for (int v_val : adj[u_val]) {
            idg[v_val]--;
            if (idg[v_val] == 0) {
                next_q_add.push_back(v_val);
            }
        }
        sort(next_q_add.begin(), next_q_add.end()); 
        for(int node_to_add : next_q_add) q_bfs.push(node_to_add);
    }
    
    if (cnt < n) { // 未能处理所有n个节点，说明存在环
        return {2, ""}; // 状态2: 矛盾
    }

    // 已处理所有n个节点 (cnt == n)
    if (is_uniq) { // 且过程中始终只有一个选择（或初始多个，但后续都唯一）
        return {1, res}; // 状态1: 顺序确定
    } else {
        return {0, ""}; // 状态0: 序列不唯一，无法确定
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        char u_char, sep_char, v_char;
        cin >> u_char >> sep_char >> v_char;
        ru[i] = u_char;
        rv[i] = v_char;
    }

    for (int k = 1; k <= m; ++k) { // 逐步加入关系
        pair<int, string> stat = get_status(k);
        if (stat.first == 1) { // 顺序确定
            cout << "Sorted sequence determined after " << k << " relations: " << stat.second << "." << endl;
            return 0;
        } else if (stat.first == 2) { // 发现矛盾
            cout << "Inconsistency found after " << k << " relations." << endl;
            return 0;
        }
        // 若 stat.first == 0，则继续加入下一个关系
    }

    // 所有关系处理完，仍未确定顺序或发现矛盾
    cout << "Sorted sequence cannot be determined." << endl;
    return 0;
}

// 复杂度分析:
// - 外层循环 m 次 (k from 1 to m)。
// - 内层 get_status 函数：
//   - 建图：O(k_cur) ≈ O(m)
//   - Kahn算法：O(n + k_cur) ≈ O(n+m) (因为边数最多是k_cur条)
// - 总时间复杂度: O(m * (n + m))。
//   对于 N=26, M=600，约为 600 * (26+600) ≈ 600 * 626 ≈ 3.7 * 10^5，可行。
// - 空间复杂度: O(n+m) (存储关系、邻接表等)。

7. 构造无环图：给无向边定向 (CF1385E Directing Edges)

CF1385E Directing Edges

题目描述

给定一个包含 个顶点和 条边的图。其中一些边是已经定向的，另一些边是无向的。你需要为所有无向边确定一个方向，使得最终得到的图是一个有向无环图 (DAG)。如果可以做到，输出 “YES” 并给出所有边的最终方向；否则输出 “NO”。

输入格式

多组测试数据。每组数据首先是 。接下来 行，每行 ： 表示有向边 ， 表示无向边 。

输出格式

对于每组数据，如果可行，输出 “YES” 和 行描述最终图的边。否则输出 “NO”。

题意分析:
核心问题是：能否将所有无向边定向，使得整个图（包括原有的有向边和新定向的无向边）变成一个DAG。

代码实现 (C++14):

// 题意概括: CF1385E. 给一些有向边和无向边，为无向边定向，
// 使得最终图为DAG。若可以，输出YES及所有边；否则NO。
// 使用Kahn算法实现。

#include<bits/stdc++.h>

using namespace std;
using ll = long long; // 竞赛习惯，此题int足够

const int MAXN = 200005; // 最大顶点数
vector<int> adj[MAXN];   // 邻接表 (仅存储初始有向边)
int idg[MAXN];           // 存储每个顶点的入度 (基于初始有向边)

// 存储原始边信息的结构体
struct Edg {
    int t; // type: 0 无向, 1 有向
    int u, v; // 边的端点
};

void slv() { // solve_test_case
    int n, m; // n_nodes, m_edges
    cin >> n >> m;

    // 初始化图结构
    for (int i = 1; i <= n; ++i) {
        adj[i].clear();
        idg[i] = 0;
    }

    vector<Edg> es; // all_original_edges, 存储所有读入的边

    for (int i = 0; i < m; ++i) {
        int _t, _u, _v; // temp type, u, v for input
        cin >> _t >> _u >> _v;
        es.push_back({_t, _u, _v});
        if (_t == 1) { // 如果是初始有向边
            adj[_u].push_back(_v);
            idg[_v]++;
        }
        // 无向边暂时只存储
    }

    queue<int> q; // Kahn算法使用的队列
    for (int i = 1; i <= n; ++i) {
        if (idg[i] == 0) {
            q.push(i);
        }
    }

    vector<int> tord; // topological_order_nodes, 存储拓扑排序结果
    vector<int> rnk(n + 1); // node_rank[u]是节点u在拓扑序中的排名 (0-indexed)
    int crnk = 0; // current_rank_assign

    while (!q.empty()) {
        int uc = q.front(); // u_current
        q.pop();

        tord.push_back(uc);
        rnk[uc] = crnk; // 分配排名
        crnk++;

        for (int vn : adj[uc]) { // v_neighbor
            idg[vn]--;
            if (idg[vn] == 0) {
                q.push(vn);
            }
        }
    }

    if (tord.size() < n) { // 如果拓扑排序未能包含所有节点
        cout << "NO\n";    // 说明仅有向边部分就已存在环
        return;
    }

    // 初始有向边构成DAG，已获得拓扑排名
    cout << "YES\n";
    for (const auto& e : es) { // 遍历所有原始边
        if (e.t == 1) { // 原始有向边，直接输出
            cout << e.u << " " << e.v << "\n";
        } else { // 原始无向边，根据拓扑排名定向
            if (rnk[e.u] < rnk[e.v]) {
                cout << e.u << " " << e.v << "\n";
            } else {
                // 由于rnk唯一，此处必为 rnk[e.v] < rnk[e.u]
                cout << e.v << " " << e.u << "\n";
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int tc; // num_test_cases
    cin >> tc;
    while (tc--) {
        slv();
    }
    return 0;
}

// 时间复杂度:
// - 对于每个测试用例：
//   - 初始化: O(N)
//   - 读输入建图(仅有向边): O(M + N)
//   - Kahn算法拓扑排序: O(N + M_directed) (M_directed是有向边数)
//   - 输出边: O(M)
// - 单次测试用例复杂度为 O(N+M)。
// - 总时间复杂度: O(sum(N) + sum(M))。
// 空间复杂度:
// - 邻接表adj: O(N + M_directed)
// - 入度数组idg: O(N)
// - 存储所有原始边es: O(M)
// - 拓扑序tord及排名rnk: O(N)
// - 队列q: O(N)
// - 单次测试用例空间复杂度为 O(N+M)。

六、解题思维与常见陷阱

1. 建模是关键

很多时候，题目不会直接说“请对这个图进行拓扑排序”。你需要从问题描述中抽象出节点和它们之间的依赖关系，构建出DAG模型。

• 识别节点：通常是任务、事件、状态、物品等。
• 识别依赖：注意关键词，如“必须在…之前”、“依赖于”、“先…后…”等。这些指明了边的方向。
• 检查是否有环：思考是否存在逻辑上的循环依赖。如果可能存在，那么拓扑排序可能不适用，或者需要先处理环（如SCC缩点）。

2. 顶点编号与数据结构

• 竞赛中顶点编号可能是0-indexed或1-indexed。代码实现时要注意统一。
• 邻接表 (vector<int> adj[MAXN]) 是存储图的常用高效方式。
• 入度数组 idg[MAXN] 是Kahn算法的核心。
• DFS的状态数组 vis[MAXN] 也很重要。

3. 处理多起点/无特定起点问题

• Kahn算法自然处理多起点（多个初始入度为0的节点）。
• DFS算法通过遍历所有未访问节点来确保覆盖所有连通分量（或者说，所有DAG的“源头”部分）。
• 在DAG上DP时，如果问题没有指定单一源点，可能需要将所有入度为0的节点（或拓扑序靠前的节点）作为DP的初始状态。

4. 常见错误与调试

• 环的判断：
  • Kahn：最后检查 res.size() 是否等于 n。
  • DFS：检查是否有边指向 vis[v] == 1 的节点。
  • 忘记判环可能导致死循环或错误结果。
• 数组大小：MAXN 是否足够大？是否考虑到顶点编号范围？
• 初始化：入度数组、DP数组、visited数组等是否正确初始化？
• 边的方向：依赖关系 (A是B的前提)，则边是从A指向B。不要搞反。
• DFS中列表添加顺序：DFS是完成时将节点加入列表 头部，或者加入尾部然后 整体反转。
• Kahn算法中队列的选择：普通队列 std::queue 用于一般拓扑排序。优先队列 std::priority_queue 用于求字典序最小/最大的拓扑排序。
• 清空数据结构（多测试用例）：在处理多个测试用例的题目时，确保每次都清空邻接表、入度数组、结果列表等。

5. 思考“逆向”问题

有时问题可以从“正向拓扑”思考，也可以从“反向拓扑”思考。
例如，如果求每个节点能到达多少个其他节点，可以在原图上以每个节点为起点跑DFS/BFS。但如果图很大，这样做效率低。
可以考虑建反图 (所有边方向颠倒)。在反图上，从节点 出发能到达的节点集合，对应于原图中能到达 的节点集合。
对于某些DP问题，在反图上跑拓扑排序可能更方便。

七、写在最后

拓扑排序，作为图论中的一个基础而重要的算法，其核心在于揭示和利用有向无环图中的偏序关系。它不仅能够直接解决依赖排序问题，更是作为许多高级算法（如图DP、关键路径分析）的基石。

通过本文的梳理，我们回顾了：

• 拓扑排序的定义及其与DAG的紧密联系。
• Kahn算法（基于BFS）和DFS算法（基于深度优先）的原理、实现、复杂度分析及特性比较。
• 拓扑排序在竞赛中的多种应用：任务调度、DAG上的DP（最长/最短路、路径计数）、字典序拓扑序列、唯一性判断、与SCC的结合，以及如P1347这样的综合问题。
• 解题时构建DAG模型、选择合适算法、规避常见陷阱的策略。