510C Fox And Names 展示了拓扑排序最直接的用途：把局部先后约束合成一个全局顺序。但在更多题目里，拓扑序只是骨架，答案还取决于我们在这个顺序上保存什么信息。

本文连续分析三道题：1385E 用拓扑位置完成构造，1572A 在拓扑边上做最长路式动态规划，909E 则把入度为零的点按执行设备分成批次。它们共享“只有前置任务完成，后继才会释放”的过程，却不能共用同一个答案变量。

1. 官方信息与训练顺序

以下题名、难度、标签和约束于 2026-09-16 通过 Codeforces 官方题目页核对。

题目 难度 官方标签 规模 本文训练点
1385E · Directing Edges 2000 constructive algorithms、dfs and similar、graphs 单组 n,m≤2×10^5，总和均不超过 2×10^5 用固定边的拓扑序决定其余边方向
1572A · Book 1800 binary search、brute force、data structures、dp、graphs、implementation、sortings 所有测试的章节数与依赖数总和不超过 2×10^5 拓扑 DP 计算最少扫描轮数
909E · Coprocessor 1900 dfs and similar、dp、graphs、greedy n,m≤10^5，输入保证依赖图无环 两类零入度点的贪心分批

建议按表中顺序练习。第一题先回答“拓扑序能否指导构造”，第二题再加入数值状态，第三题最后处理“同一批内可以继续释放任务”的操作语义。

2. 共同骨架：入度何时变成零

对一条边 u → v，含义是 u 必须先完成。Kahn 算法维护每个点尚未完成的前驱数 indegree[v]：

  1. 先把所有零入度点放入容器；
  2. 取出一个可执行点 u；
  3. 删除它的所有出边，即令每个后继的入度减一；
  4. 某个后继第一次降到零时，它才成为新的可执行点。

如果最终处理的点少于 n，未处理部分一定含有有向环。反过来，DAG 必然至少存在一个零入度点，所以这个过程能处理全部顶点。

三题真正的差别在于“零入度之后怎么办”：

题目 零入度点的用途 额外状态
1385E 记录它在一个合法拓扑序中的位置 position[u]
1572A 用它向后继传播最少扫描轮数 round[u]
909E 按主处理器或协处理器放入不同队列 两个就绪队列与调用次数

3. 第一题：1385E Directing Edges

3.1 题意压缩

图中有两类边：

  • 已经定向的边不能改变；
  • 无向边必须选择一个方向。

目标是让最终所有边组成 DAG。朴素地逐条尝试两个方向会产生 2^k 种方案，其中 k 是无向边数，显然无法承受。

关键问题不是“每条无向边选哪边”，而是“能否先找出一个所有边都愿意服从的全局次序”。

3.2 只检查固定的有向边

先忽略全部无向边，只对固定有向边建图。

  • 如果固定边已经形成环，无论怎样定向其他边，这个环都会保留，答案必为 NO；
  • 如果固定边是 DAG，就取它的任意拓扑序，并记录每个顶点的位置。

对于无向边 {u,v}，让拓扑位置较小的端点指向位置较大的端点。这样固定边和新定向的边都会沿同一个顺序向前。

3.3 手工演算

设固定边为 1→4、3→4，另有无向边 {1,2}、{2,3}。固定子图的一种拓扑序是：

顶点 1 2 3 4
pos 0 1 2 3

于是两条无向边分别定向为 1→2、2→3。最终每条边都让 pos 严格增加，因此不可能绕一圈回到起点。

3.4 正确性证明

必要性。 如果固定有向边存在环，这些边的方向不可修改，任何完整定向仍包含该环，所以无解。

充分性。 假设固定有向边是 DAG。取其拓扑序 order。固定边按照拓扑序定义都从较早位置指向较晚位置；每条无向边也被我们按同一规则定向。因此最终图的每条边 u→v 都满足 pos[u] < pos[v]。若存在有向环，沿环走一圈会得到位置严格递增后又回到原位置的矛盾，所以最终图无环。

这也说明构造不需要动态维护环：只要先固定一个拓扑序，所有剩余选择一次完成。

3.5 完整 C++17 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int type;
    int from;
    int to;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int testCases;
    cin >> testCases;
    while (testCases--) {
        int n, m;
        cin >> n >> m;

        vector<Edge> edges;
        edges.reserve(m);
        vector<vector<int>> graph(n);
        vector<int> indegree(n, 0);

        for (int i = 0; i < m; ++i) {
            int type, x, y;
            cin >> type >> x >> y;
            --x;
            --y;
            edges.push_back({type, x, y});
            if (type == 1) {
                graph[x].push_back(y);
                ++indegree[y];
            }
        }

        queue<int> ready;
        for (int vertex = 0; vertex < n; ++vertex) {
            if (indegree[vertex] == 0) ready.push(vertex);
        }

        vector<int> order;
        order.reserve(n);
        while (!ready.empty()) {
            int vertex = ready.front();
            ready.pop();
            order.push_back(vertex);
            for (int next : graph[vertex]) {
                --indegree[next];
                if (indegree[next] == 0) ready.push(next);
            }
        }

        if (static_cast<int>(order.size()) != n) {
            cout << "NO\n";
            continue;
        }

        vector<int> position(n);
        for (int i = 0; i < n; ++i) position[order[i]] = i;

        cout << "YES\n";
        for (const Edge& edge : edges) {
            if (edge.type == 1 || position[edge.from] < position[edge.to]) {
                cout << edge.from + 1 << ' ' << edge.to + 1 << '\n';
            } else {
                cout << edge.to + 1 << ' ' << edge.from + 1 << '\n';
            }
        }
    }
}

时间复杂度 O(n+m)，空间复杂度 O(n+m)。

4. 第二题：1572A Book

4.1 为什么普通拓扑层数不够

第 i 章列出若干前置章节。我们反复从第 1 章读到第 n 章：读到某章时，如果全部前置章节已经理解，就立刻理解它；否则这一轮不会回头，只能等下一次从头开始。

若只按拓扑层数分组，会漏掉章节编号带来的先后差异。例如依赖边 2→4 可以在同一轮完成，因为先读第 2 章再到第 4 章；边 4→2 则至少跨一轮，因为理解第 4 章时，这一轮的第 2 章已经错过。

4.2 状态与转移

令 round[v] 表示理解章节 v 最早需要读到第几轮。所有无前置章节的初值都是 1。

对依赖边 u→v：

1
round[v] = max(round[v], round[u] + (u > v ? 1 : 0))
  • 若 u < v，同一轮先理解 u，之后还能读到 v，不增加轮数；
  • 若 u > v，本轮到达 u 时已经越过 v，必须等下一轮，增加 1。

一个章节必须等待所有前驱，因此取所有前驱贡献的最大值。Kahn 算法在 v 入度降到零时，已经收齐它的全部前驱贡献。

4.3 手工演算

设依赖为 2→4、4→1、1→3。

边 编号关系 轮数变化 结果
2→4 2<4 不加轮 round[4]=1
4→1 4>1 加一轮 round[1]=2
1→3 1<3 不加轮 round[3]=2

第一轮可以理解 2、4；第二轮理解 1、3，答案为 2。这个结果与逐轮模拟一致，但动态规划只沿每条边处理一次。

4.4 正确性证明

按任意拓扑序处理顶点。对无前驱顶点，一轮即可理解，初值 1 正确。

假设所有前驱 u 的 round[u] 都已是最早轮数。章节 v 不可能早于任何前驱完成：若 u<v，最早可在 round[u] 的同一轮到达 v；若 u>v，那一轮已经越过 v，最早只能在 round[u]+1。因此所有转移给出的最大值是必要下界。

另一方面，到这个最大轮数时，每个前驱都已在本轮较早位置或此前轮次完成，所以 v 确实可以被理解。状态既不低估也不高估。若处理数不足 n，依赖图含环，环中没有章节能率先被理解，应输出 -1。

4.5 完整 C++17 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int testCases;
    cin >> testCases;
    while (testCases--) {
        int n;
        cin >> n;
        vector<vector<int>> graph(n);
        vector<int> indegree(n, 0);

        for (int chapter = 0; chapter < n; ++chapter) {
            int count;
            cin >> count;
            indegree[chapter] = count;
            while (count--) {
                int prerequisite;
                cin >> prerequisite;
                --prerequisite;
                graph[prerequisite].push_back(chapter);
            }
        }

        queue<int> ready;
        vector<int> round(n, 1);
        for (int chapter = 0; chapter < n; ++chapter) {
            if (indegree[chapter] == 0) ready.push(chapter);
        }

        int processed = 0;
        int answer = 1;
        while (!ready.empty()) {
            int chapter = ready.front();
            ready.pop();
            ++processed;
            answer = max(answer, round[chapter]);

            for (int next : graph[chapter]) {
                int extraRound = chapter > next ? 1 : 0;
                round[next] = max(round[next], round[chapter] + extraRound);
                --indegree[next];
                if (indegree[next] == 0) ready.push(next);
            }
        }

        cout << (processed == n ? answer : -1) << '\n';
    }
}

时间复杂度 O(n+m)，空间复杂度 O(n+m)，其中 m 是依赖总数。

5. 第三题：909E Coprocessor

5.1 操作语义比拓扑序更重要

每个任务只能在主处理器或协处理器上执行。主处理器执行不计调用次数；一次协处理器调用可以提交一组任务，并允许这组任务内部存在已经满足方向的依赖。目标是最小化协处理器调用次数。

输入中的 T1 T2 表示任务 T1 依赖 T2，建图时必须加入 T2→T1。把方向写反会得到另一张仍可能无环的图，是最隐蔽的错误之一。

普通 FIFO 拓扑队列只保证合法，却不保证调用次数最少。若一个主处理器任务和协处理器任务同时就绪，先免费完成主任务可能释放更多协处理器任务，让它们并入下一次调用；先调用协处理器则可能平白增加一个批次。

5.2 两个就绪队列

分别维护：

  • mainReady：入度为零且只能在主处理器执行；
  • coprocessorReady：入度为零且只能在协处理器执行。

每一轮先把 mainReady 完全清空，因为这些操作免费。若仍有协处理器任务，就开始一次调用，并把当前可执行的协处理器任务及其在本批内继续释放的协处理器任务全部完成；新释放的主处理器任务留到本次调用结束后处理。

5.3 为什么一个调用能包含后续释放的协处理器任务

假设协处理器任务 a 完成后，任务 b 的入度降为零，而且 b 也属于协处理器。把 a 与 b 放在同一次调用中是合法的：题目允许一个任务的依赖已经完成，或者也包含在同一个提交集合里。由于原图是 DAG，这个集合内部总能按拓扑顺序执行。

主处理器任务不能塞进这次调用，所以一旦协处理器闭包耗尽，就必须返回主处理器继续执行。

5.4 手工演算

设任务类型与依赖如下：

任务 设备 前置任务
0 主处理器 无
1 协处理器 0
2 协处理器 1
3 主处理器 2
4 协处理器 3

执行过程为：

阶段 完成任务 累计调用次数
免费阶段 0 0
第一次协处理器调用 1、2 1
免费阶段 3 1
第二次协处理器调用 4 2

任务 1 和 2 虽有依赖，仍能放入同一次调用；任务 3 强制把协处理器任务分成两个批次。

5.5 贪心正确性证明

引理一：调用协处理器前，完成全部当前可执行的主任务不会使答案变差。 主任务不消耗调用次数，只可能删除出边、释放更多任务，不会让任何已就绪任务重新变得不可执行。因此任意最优方案都可调整为先完成这些主任务。

引理二：一次调用中加入所有可由协处理器任务继续释放的协处理器任务不会使答案变差。 这些任务与它们在本批中的前驱一起构成 DAG，可以在一次调用内部按拓扑序执行。提前完成它们只会继续释放后继，不会制造新依赖。

根据两个引理，每当免费闭包耗尽而仍有协处理器任务就绪时，任何方案都至少需要一次新调用；算法恰好增加一次，并完成这次调用所能覆盖的最大协处理器闭包。逐批应用即可得到最少调用次数。

5.6 完整 C++17 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<int> device(n);
    for (int& value : device) cin >> value;

    vector<vector<int>> graph(n);
    vector<int> indegree(n, 0);
    for (int i = 0; i < m; ++i) {
        int task, prerequisite;
        cin >> task >> prerequisite;
        graph[prerequisite].push_back(task);
        ++indegree[task];
    }

    queue<int> mainReady;
    queue<int> coprocessorReady;
    for (int task = 0; task < n; ++task) {
        if (indegree[task] != 0) continue;
        if (device[task] == 0) mainReady.push(task);
        else coprocessorReady.push(task);
    }

    auto complete = [&](int task) {
        for (int next : graph[task]) {
            --indegree[next];
            if (indegree[next] != 0) continue;
            if (device[next] == 0) mainReady.push(next);
            else coprocessorReady.push(next);
        }
    };

    int calls = 0;
    int completed = 0;
    while (completed < n) {
        while (!mainReady.empty()) {
            int task = mainReady.front();
            mainReady.pop();
            ++completed;
            complete(task);
        }

        if (coprocessorReady.empty()) break;
        ++calls;
        while (!coprocessorReady.empty()) {
            int task = coprocessorReady.front();
            coprocessorReady.pop();
            ++completed;
            complete(task);
        }
    }

    cout << calls << '\n';
}

题目保证输入为 DAG，因此最终会完成全部任务。时间复杂度 O(n+m)，空间复杂度 O(n+m)。

6. 三题为什么不能只背一个模板

比较项 1385E 1572A 909E
图是否可能有环 固定边可能有环 依赖可能有环 保证无环
容器 一个零入度队列 一个零入度队列 按设备拆成两个队列
核心状态 拓扑位置 最早轮数 当前批次与调用次数
贪心选择 所有新边沿拓扑序向前 无，取所有前驱最大值 免费任务优先，同类协任务成批
失败条件 固定边处理不足 n 处理不足 n 题目保证不会失败

可以把三题压缩成三个问题：

  1. 只要所有边都服从同一拓扑序，能否直接完成构造？
  2. 后继被释放时，还需要从前驱继承什么代价？
  3. 多个零入度点同时存在时，处理顺序是否影响目标函数？

7. 边界与常见错误

场景 正确处理 常见错误
1385E 图不连通 所有分量的零入度点都进入队列 只从顶点 1 开始 DFS
1385E 无向边很多 统一按 position 定向 每加一条边重新判环
1572A 无前置章节 round=1 初始化为 0，少算第一轮
1572A 边 u→v u>v 才加一轮 把条件写成 u<v
1572A 存在依赖环 处理数不足时输出 -1 只输出当前最大轮数
909E 输入 T1 T2 建边 T2→T1 按输入顺序建成 T1→T2
909E 同类协任务形成链 可放入同一次调用 每层拓扑都增加调用次数
909E 主任务与协任务同时就绪 先清空主任务 用单个 FIFO 队列随缘处理

8. 独立验证

验证脚本 tests/verify-topological-three-article.cjs 会提取并以 -std=c++17 -Wall -Wextra -pedantic 编译三份代码，并执行三类独立检查：

  • 对 1385E，独立检测固定有向子图是否有环，并验证输出保留固定方向、覆盖全部边且最终无环；
  • 对 1572A，在小图上直接逐轮从第 1 章扫描到第 n 章，与拓扑 DP 比较；
  • 对 909E，在小 DAG 上用状态最短路枚举免费主任务与一次调用可提交的协处理器集合，核对最少调用数。

测试还包含官方样例、空依赖、长链、反向编号链、全部同类任务和大规模边界。这样可以分别发现“方向写反”“轮数条件反了”和“把同一调用拆成多层”三类错误。

9. 继续学习

拓扑排序题的重点通常不在“会不会把入度减一”，而在于解释：顶点进入零入度集合之后，题目允许我们立刻做什么，以及不同的可执行顺序是否会改变答案。