拓扑排序

引入

在大学的课程体系中，例如有：「程序设计」、「算法语言」、「高等数学」、「离散数学」、「编译技术」、「普通物理」、「数据结构」、「数据库系统」等课程。

有些课程有先修要求：

• 学「数据结构」之前必须完成「离散数学」。
• 有了「数据结构」的基础，才能继续学习「编译技术」。

这些课程可以看作图中的点（顶点），课程间的先修关系可视为图中的有向边。

教务处需要按照这些依赖关系，排出合理的课程顺序，使得每门课程的前置条件都已被满足。

这就是典型的 拓扑排序 问题。

---

概念

拓扑排序（Topological Sorting） 是图论中的一种排序方法。

它的目标是对一个 有向无环图（DAG） 中的所有节点进行排序，使得对于每条有向边 $(u, v)$，节点 $u$ 排在节点 $v$ 的前面。

• 拓扑排序只适用于 有向无环图（DAG）。
• 如果图中存在边 $i \rightarrow j$，则 $j$ 依赖 $i$，$i$ 必须排在 $j$ 前面。
• 如果存在从 $i$ 到 $j$ 的路径，则称 $j$ 间接依赖 $i$。
• 拓扑排序要求：排序后，任意节点都不会依赖于它后面的节点。
• 若图中存在环（依赖关系冲突），则无法进行拓扑排序。

Kahn 算法

由 Arthur B. Kahn 于 1962 年提出，基于入度的广度优先思想。

步骤：

• 计算所有节点入度
• 将入度为零的节点入队
• 依次出队并移除节点及其出边，更新相邻节点入度，若入度为零则入队

具体实现

• 使用数组存储入度信息。例如定义 int in[N]。
• 使用队列（Queue）动态维护所有当前入度为 $0$ 的顶点。
• 时间复杂度：$O(|V| + |E|)$

---

实现代码

int n, m;
cin >> n >> m;
while (m--)
{
    int u, v;
    cin >> u >> v;
    e[u].push_back(v);
    in[v]++; // 点 v 的入度加 1
}
queue<int> q;
for (int i = 1; i <= n; i++) 
    if (in[i] == 0) // 入度为 0 的点入队
        q.push(i);
vector<int> ans;
while (q.size())
{
    int u = q.front();
    q.pop();
    ans.push_back(u);
    for (auto v : e[u])
    {
        in[v]--; // 点 v 的入度减 1，相当于删去 u->v 这条边
        if (in[v] == 0) q.push(v); // 入度为 0 的点入队
    }
}
if (ans.size() != n) cout << "-1"; // 有环
else for (auto x : ans) cout << x << " ";

---

总结

• 计算入度：遍历所有边 $O(m)$
• 使用队列处理每个节点一次：$O(n)$
• 更新入度总操作：遍历所有边 $O(m)$
• 综合：$O(n+m)$

---

DFS 实现拓扑排序

DFS 版拓扑排序使用一种形象的 三色染色 策略，模拟节点的访问状态：

• 白色（0）：尚未访问。
• 灰色（1）：正在访问。
• 黑色（2）：已完成访问。

一旦在 DFS 中遇到一条指向 色 节点的边，说明图中存在 回边 $\Rightarrow$ 有环！

流程

• 从每个未访问 白色 节点开始 DFS。
• 每次递归处理完所有 后继 后，将当前节点 后序 加入结果列表。
• 最后将结果列表 $\texttt{reverse}$，得到合法的拓扑序列。

为何后序入栈？

假设有边 $u \to v$，DFS 会先处理 $v$，最后处理 $u$。

所以栈里先是 $v$ 再是 $u$，反转后保证 $u$ 在 $v$ 之前。

---

代码

// 返回 false 表示图中存在环
bool dfs(int u) 
{
    vis[u] = 1; // 灰色：访问中
    for (auto v : e[u]) 
    {
        if (vis[v] == 1) return false; // 遇到灰色，存在环！
        if (vis[v] == 0 && !dfs(v)) return false; // 向下递归
    }
    vis[u] = 2; // 黑色：访问完成
    ans.push_back(u); // 后序入栈
    return true;
}

int main() 
{
    for (int i = 1; i <= n; i++) 
    {
        if (vis[i] == 0) 
        {
            if (!dfs(i)) 
            {
                cout << "-1"; // 图中有环
                return 0;
            }
        }
    }
    reverse(ans.begin(), ans.end()); // 反转得到拓扑序
    for (auto x : ans) cout << x << " ";
}

---

总结

• 时间复杂度：$O(n + m)$
• 空间复杂度：邻接表存图：$O(n + m)$

特例

如果已知图是 DAG，可省略环检测逻辑，代码更简洁：

void dfs(int u) 
{
    vis[u] = true;
    for (int v : e[u])
        if (!vis[v]) 
            dfs(v);
    topo.push_back(u); // 后序加入
}
for (int i = 1; i <= n; i++)
{
    if (!vis[i]) // 尝试所有起点 i
    {
        dfs(i);
    }
}

注意： 此方法假设图中不存在环，适用于图结构已验证为 DAG 的场景（如某些题目保证无环）。

---

例题

[ABC223D] Restricted Permutation

题意： 给定正整数 $n,m$ 以及 $m$ 对关系 $(a_i,b_i)$，要求在排列 $p$（是 $1\sim n$ 的一个排列）中，$\forall i\in[1,m]$，元素 $a_i$ 必须出现在 $b_i$ 之前；在所有可行排列中，输出字典序最小者，若不存在则输出 $\texttt{-1}$。

$2\le n,m\le2\times10^5$，所有 $a_i\ne b_i$。

思路： 将 $1\sim n$ 看作图中 $n$ 个节点。

对每个关系 $(a_i,b_i)$ 建一条有向边 $a_i\to b_i$。

题目即 在此有向图上求字典序最小的拓扑排序。

思路：

用 小根堆（priority_queue<int, vector<int>, greater<int>>）维护当前所有入度为 $0$ 的节点，确保每次取出的都是最小编号。

最终若答案序列长度为 $n$ 则输出，否则输出 $\texttt{-1}$（存在环）。

时间复杂度：$\displaystyle O\bigl((n+m)\log n\bigr)$

---

CF1385E - Directing Edges

题意： 给定一个混合图：部分边已定向，部分边是无向的。

• 要求：为所有无向边指定方向，使得最终图成为一个有向无环图（DAG）。

思路：

• 对已有的定向边执行标准拓扑排序（Kahn 或 DFS）。
• 出队（或出栈）时，记录每个节点的 拓扑序 $topo[u]$。
  • 初始化一个变量 cnt = 0。
  • 出队时执行 topo[u] = ++cnt，记录点 $u$ 是第 $cnt$ 次访问到的。
  • 这样就可以用 topo[u] 和 topo[v] 的值比较谁先访问谁后访问。来决定边的方向。
• 若过程中发现环，则立即停止：无法构造 DAG，答案为 $\texttt{NO}$。

拓扑序 反映节点在 DAG 中的先后关系：值越小，越早访问。

处理无向边

对每条无向边 ${u,v}$，比较两端的拓扑序大小关系：

\[ topo[u]\;<\;topo[v] \quad\Longrightarrow\quad \text{将边定向为 }\ u\to v; \quad\text{否则 }\ v\to u. \]

为什么可行？

拓扑序保证：若 $topo[u]<topo[v]$，在已有定向部分中没有从 $v$ 到 $u$ 的路径。

定向后不会引入新环，最终整个图仍保持 DAG 特性。

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

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n, m;
        cin >> n >> m;
        vector<pair<int, int>> adj; // 存无向边
        vector<vector<int>> e(n + 1);
        vector<int> in(n + 1);
        while (m--)
        {
            int t, u, v;
            cin >> t >> u >> v;
            if (!t) adj.push_back({u, v});
            else 
            {
                e[u].push_back(v);
                in[v]++;
            }
        } 
        queue<int> q;
        for (int i = 1; i <= n; i++)
            if (!in[i])
                q.push(i);
        int cnt = 0;
        vector<int> topo(n + 1); 
        while (q.size())
        {
            int u = q.front();
            q.pop();
            topo[u] = ++cnt;
            for (auto v : e[u]) 
            {
                --in[v];
                if (!in[v]) 
                    q.push(v);
            }
        }
        if (cnt != n)
        {
            cout << "NO\n";
        }
        else
        {
            cout << "YES\n";
            // 先输出有向边
            for (int i = 1; i <= n; i++)
                for (auto j : e[i])
                    cout << i << " " << j << "\n";
            // 在输出无向边
            for (auto it : adj)
            {
                int u = it.first, v = it.second;
                if (topo[u] < topo[v])
                    cout << u << " " << v << "\n";
                else 
                    cout << v << " " << u << "\n";
            } 
        }
    } 
    return 0;
}

---

[ABC245F] Endless Walk

题意： 给定一个点数为 $n$、边数为 $m$ 的 有向图，你需要判断：

• 有多少个点 $v$，从 $v$ 出发可以 一直走不停？
• 即可以走到一个环上。
• $1 \le n, m \le 2 \times 10^5$

思路：

什么时候可以无限走？

• 一个点本身在 环 中，可以在环里兜圈子。
• 或者，它能走到某个 环 上，最后进入循环。

正向难以处理。从每个点出发找 是否能到某个环 太慢，复杂度高！

换个角度 —— 倒着思考！建立反图思考该问题：

核心思路：从 不能无限走 的点出发，反推出影响范围。

• 若某个点 出度为 0，说明它 无法继续前进。
• 如果你能走到这样的 死路 节点，说明你也走不远。

做法：

• 将原图 反向建图边 $u \to v$ 变成 $v \to u$。
• 对反图进行 拓扑排序，从 入度为 0 的点 开始剥离。
• 所有能被剥离的点，都是 最终无法无限走下去 的点。

反图中入度为 $0$ 相当于原图出度为 $0$，能被这些点访问到的点，说明在原图中可以走向这些出度为 $0$ 的点从而无法永远走下去。

cin >> n >> m;
for (int i = 1; i <= m; i++)
{
    int u, v;
    cin >> u >> v;
    e[v].push_back(u);
    in[u]++;
}
queue<int> q;
for (int i = 1; i <= n; i++)
{
    if (!in[i])
    {
        q.push(i);
    }
}
while (q.size())
{
    int u = q.front();
    q.pop();
    ans++;
    for (int v : e[u])
    {
        in[v]--;
        if (!in[v])
        {
            q.push(v);
        }
    }
}
cout << n - ans;

---

[HNOI2015] 菜肴制作

题意： ATM 大酒店为小 A 准备了 $n$ 道菜肴，并给每道菜编号 $1$ 到 $n$，编号越小，预估质量越高。现在有 $m$ 条形如 $(i, j)$ 的限制，表示 $i$ 菜必须在 $j$ 之前制作。

目标：在满足所有限制的前提下，让质量高的菜尽量先被制作。

换句话说：优先让 $1$ 号菜靠前，若有冲突就让 $2$ 号靠前，以此类推。

样例分析

样例 $1$：

• $n = 4$，限制为 $(3,1), (4,1)$
• 虽然 $1$ 质量最高，但它有前置条件
• 要满足优先顺序，必须尽量先安排 $3$ 和 $4$
• 因此输出：3 4 1 2。

样例 $2$：

• $n = 5$，限制为 $(5,2), (4,3)$
• 尽量让 $1$、$2$、$3$ 等高质量菜靠前，但要满足依赖关系
• 因此输出：1 5 2 3 4。

容易误解为求字典序最小的拓扑序，，但这并不满足题目要求！（样例 $2$ 可以看出）

正解：逆向建图 + 大根堆拓扑排序

• 为了让小编号（高质量）的菜尽量靠前

• 就要让大编号的菜尽量靠后（滞后进入排序

• 在原图的基础上 建反图，将每条边反向

• 在反图上进行 拓扑排序
• 用 大根堆 维护当前入度为 $0$ 的点 —— 每次选最大的，保证小的留在前面。
• 输出时主要反向输出。

---

可达性统计

题意： 给定一张 $N$ 个点 $M$ 条边的有向无环图，分别统计从每个点出发能够到达的点的数量。$1 \le N,M \le 30000$。

思路：

• 将图进行拓扑排序
• 逆序遍历拓扑序（从终点往前回推）
• 对于每个点 $u$，它可以到达的点集合 = 自己 + 所有 $v \in u$ 的出边所能到达的点

朴素做法需要枚举 $v$ 的连通性，然后合并到 $u$ 里，即 f[u][i] = f[u][i] || f[v][i]。

如此的时间复杂度为 $O((n+m)\cdot n)$。

考虑使用 bitset 优化，

• 每个点维护一个 bitset 集合，表示它能到达的点
• 拓扑排序后，逆序处理每个点
• 若 $u \to v$，则将 $v$ 的 bitset 合并进 $u$

bitset<MAXN> f[MAXN];
for (int i = n; i >= 1; --i) 
{
    int u = topo[i]; // 拓扑序第 i 个点的编号
    f[u][u] = 1;
    for (int v : e[u])
        f[u] |= f[v];
}

时间复杂度：$O(\frac{N^2}{w})$

DFS做法

• 使用 DFS 进行拓扑排序
• 回溯时进行集合的并。

void dfs(int u)
{
    if (vis[u]) return;
    vis[u] = true;
    for (auto v : e[u])
    {
        dfs(v);
        f[u] |= f[v];
    }
}
int main() 
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) f[i][i] = 1;
    while (m--)
    {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
    }
    for (int i = 1; i <= n; i++)
    {
        dfs(i);
        cout << f[i].count() << "\n";
    }
    return 0;
}