拓扑排序

概念

给定一张有向无环图，将所有顶点排序，排序后的序列 $A$ 满足：对于图中的每条有向边 $(u,v)$，$u$ 在 $A$ 中的位置比 $v$ 在 $A$ 中的位置小，即 $u$ 在 $v$ 之前出现。则称 $A$ 为该图的顶点的一个拓扑序列。

如下图的一个拓扑序列是：$2\to 8\to 0\to 3\to 7\to 1\to 5\to 6\to 9\to 4\to 11\to 10\to 12$。

拓扑序列不唯一！

拓扑排序只能应用于有向无环图（DAG）：如果图中存在环，环上的顶点互为前置，无法排出合法序列。

拓扑排序的主要应用：

• 判断有向图是否存在环（拓扑序列包含全部顶点则无环，否则有环）；
• 按拓扑序做 DP：DAG 上的 DP 天然满足无后效性（如最长路、关键路径）；
• 处理"先后依赖"类问题（AOV 网，例如课程安排、工程调度）。

Kahn 算法

设 $e[u]$ 存 $u$ 的所有邻点，$t$ 存拓扑序列，$din[u]$ 存点 $u$ 的入度。

Kahn 的算法核心是用队列维护一个入度为 $0$ 的顶点集合。

算法步骤：

1. 初始时，队列 $q$ 压入所有入度为 $0$ 的顶点。
2. 每次从 $q$ 弹出一个顶点 $u$，将 $u$ 加入 $t$，并将 $u$ 的所有邻点的入度减 $1$，即删除 $u$ 的所有出边。
3. 若 $u$ 的邻点 $v$ 的入度变为 $0$，则将 $v$ 压入 $q$。
4. 重复步骤 2 到 3，直到 $q$ 为空。

Kahn 算法的时间复杂度是 $O(V+E)$，其中 $V$ 是顶点数，$E$ 是边数。

vector<int> e[MAXN], t;
int din[MAXN];

void Kahn() {
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (!din[i]) {
            q.push(i);
        }
    }

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

        t.push_back(u);
        for (int v : e[u]) {
            din[v]--;
            if (!din[v]) {
                q.push(v);
            }
        }
    }

    if (t.size() == n) {
        for (int i = 0; i < n; i++) {
            cout << t[i] << " ";
        }
    } else {
        cout << "图中存在环" << endl;
    }
}

DFS 算法

设 $e[u]$ 存 $u$ 的所有邻点，$t$ 存拓扑序列，$c[u]$ 存点 $u$ 的颜色。

$c[u]=\{-1,0,1\}$，表示 $u$ 初次访问、未访问、已回溯。

DFS 的算法核心是变色，搜索的过程中给节点进行染色，如果存在拓扑序列，则每个节点的颜色都会经历 $0\to -1\to 1$ 的过程。

算法步骤：

1. 初始时每个节点都为 $0$，即未访问。
2. 枚举每个节点 $u$ ，执行 DFS，进入节点 $u$ 时，将 $u$ 的颜色置为 $-1$，然后枚举 $u$ 的邻点 $v$，如果 $v$ 的颜色为 $0$，说明 $v$ 尚未访问，则递归进入 $v$。
3. 如果枚举完 $u$ 的所有邻点后，没有发现环，则 $u$ 的颜色置为 $1$，并将 $u$ 加入 $t$。
4. 如果发现 $u$ 的某一邻点 $v$ 的颜色为 $-1$，说明回到了祖先节点，则说明存在环，则停止搜索，一路返回 false，退出程序。

DFS 算法的时间复杂度是 $O(V+E)$，其中 $V$ 是顶点数，$E$ 是边数。

vector<int> e[MAXN], t;
int c[MAXN];

bool DFS(int u) {
    c[u] = -1;
    for (int v : e[u]) {
        if (c[v] == -1) return false;
        else if (c[v] == 0) {
            if (!DFS(v)) return false;
        }
    }
    c[u] = 1;
    t.push_back(u);
    return true;
}

void topoSort() {
    memset(c, 0, sizeof(c));
    for (int i = 1; i <= n; i++) {
        if (c[i] == 0) {
            if (!DFS(i)) {
                cout << "图中存在环" << endl;
                return;
            }
        }
    }
    reverse(t.begin(), t.end());
    for (int i = 0; i < n; i++) {
        cout << t[i] << " ";
    }
}

思考：如何求字典序最大 / 最小的拓扑序列？

Kahn 算法每次从"入度为 $0$ 的顶点集合"中任取一个点，取出顺序就是拓扑序。把普通队列换成优先队列：每次取当前入度为 $0$ 且编号最小（最大）的顶点，即可得到字典序最小（最大）的拓扑序列。

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

const int N = 100010, M = 200010;
int h[N], e[M], ne[M], idx;
int din[N], ans[N];
int n, m, cnt;

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

// 字典序最小的拓扑序列（小根堆），存在环时返回 false
bool topo_min() {
    priority_queue<int, vector<int>, greater<int>> q;
    for (int i = 1; i <= n; i++)
        if (!din[i]) q.push(i);

    while (q.size()) {
        int u = q.top();
        q.pop();
        ans[++cnt] = u;

        for (int i = h[u]; i != -1; i = ne[i]) {
            int v = e[i];
            if (--din[v] == 0) q.push(v);
        }
    }

    return cnt == n;
}

int main() {
    cin >> n >> m;
    memset(h, -1, sizeof h);

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        add(a, b);
        din[b]++;
    }

    if (!topo_min()) puts("图中存在环");
    else for (int i = 1; i <= n; i++) cout << ans[i] << ' ';

    return 0;
}

字典序最大只需把 priority_queue<int, vector<int>, greater<int>> 换成默认的 priority_queue<int>（大根堆）。复杂度 $O(E+V\log V)$。

经典题型

利用拓扑排序算法判断有向图中是否存在环

洛谷 P1347. 排序

题意：给定 $n$ 个大写字母变量和 $m$ 条形如 A < B 的关系，按输入顺序逐条加入，输出最早出现的三种情况之一：出现矛盾、能唯一确定所有变量的总顺序、全部处理完仍无法确定。

思路：每加入一条关系就跑一遍 Kahn 算法——出现环（队列提前变空）则矛盾；拓扑序列唯一且包含全部顶点则顺序确定；否则继续读入下一条。该题与仓库题解 AcWing 343. 排序 是同一道题，那里的 Floyd 传递闭包做法也可以完成判定。

拓扑排序实现：

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

const int MAXN = 30;
vector<int> e[MAXN], t;
vector<string> vs;
int n, m, din[MAXN], cpdin[MAXN];
set<int> st;

bool topoSort(int size, bool &unique) {
    for (int i = 0; i < MAXN; i++) cpdin[i] = din[i];
    t.clear();

    queue<int> q;
    for (int i = 0; i < MAXN; i++) {
        if (st.count(i) && !cpdin[i]) {
            q.push(i);
        }
    }

    while (!q.empty()) {
        if (q.size() > 1) unique = false;
        int u = q.front();
        q.pop();

        t.push_back(u);
        for (int v : e[u]) {
            cpdin[v]--;
            if (!cpdin[v]) {
                q.push(v);
            }
        }
    }

    return t.size() == size;
}

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

    for (int i = 1; i <= m; i++) {
        string s; cin >> s;
        e[s[0] - 'A'].push_back(s[2] - 'A');
        din[s[2] - 'A']++;
        st.insert(s[0] - 'A');
        st.insert(s[2] - 'A');

        bool unique;
        bool flag = topoSort(st.size(), unique);

        if (!flag) {
            printf("Inconsistency found after %d relations.", i);
            return 0;
        }

        if (unique && st.size() == n) {
            printf("Sorted sequence determined after %d relations: ", i);
            for (int i = 0; i < t.size(); i++) {
                putchar(char(t[i] + 'A'));
            }
            puts(".");
            return 0;
        }
    }

    puts("Sorted sequence cannot be determined.");


    return 0;
}

通过拓扑排序使图的顶点分层，使不同层次的顶点之间满足无后效性

洛谷 P1983. 车站分级

题意：$n$ 个车站、$m$ 趟列车，每趟列车在其行驶区间内停靠若干车站；停靠车站的等级必须严格高于区间内未停靠的车站。求最少需要的等级数。

思路：对每趟列车，把区间内所有未停靠站向停靠站连有向边（等级低 → 等级高，注意判重）。由此建出的图一定是 DAG，按拓扑序 DP 求最长链长度，即为最少等级数。核心递推：

// level[u] 表示车站 u 的等级，初始均为 1，q 为 Kahn 算法的队列
int res = 1;
while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int v : e[u]) {
        level[v] = max(level[v], level[u] + 1);
        res = max(res, level[v]);
        if (--din[v] == 0) q.push(v);
    }
}
cout << res << endl;

具体代码见：洛谷 P1983. 车站分级