拓扑排序擅长处理没有环的依赖图。但是，遇到环不一定意味着问题无解：有时环表示一组必须一起考虑的顶点。先把“互相可达”的点压成一个整体，再研究整体之间的单向关系，就能把一般有向图变成 DAG。

本篇依次解决三个问题：每个整体内部怎样选点、怎样让首都覆盖所有整体、怎样找到不会牵连外部的最小维护集合。建议已了解 DFS、邻接表和有向可达性后阅读；不需要先背 Tarjan 模板。

三题路线与官方信息

题目 官方难度 官方标签 本篇训练重点
427C Checkposts 1700 dfs and similar、graphs、two pointers 分量内最小费用与方案乘法
999E Reachability from the Capital 2000 dfs and similar、graphs、greedy 未覆盖 DAG 的源分量
949C Data Center Maintenance 1900 dfs and similar、graphs 从冲突条件建蕴含边，选择汇分量

题名、难度、标签与下文约束于 2026-10-02 核对官方题页。官方标签原样保留；例如 427C 虽带 two pointers 标签，本篇解法并不使用双指针。三题不是机械递增的难度阶梯，而是同一结构的三种用途。

题目 规模与数据范围 时空限制
427C 1 ≤ n ≤ 100000，0 ≤ m ≤ 300000，0 ≤ 费用 ≤ 10⁹ 2 秒，256 MB
999E 1 ≤ n ≤ 5000，0 ≤ m ≤ 5000，1 ≤ s ≤ n 2 秒，256 MB
949C 2 ≤ n ≤ 100000，1 ≤ m ≤ 100000，2 ≤ h ≤ 100000，0 ≤ uᵢ < h 1 秒，512 MB

前两题的有向边没有自环、没有同方向重复边；949C 的客户连接两个不同数据中心，初始维护小时不同，但客户对可以重复。以下代码不依赖边去重。

从互相可达到缩点

如果 a 能走到 b，b 也能走到 a，就把它们视为同一类。这是等价关系：自身可达、互相对称，而且路径可以拼接，所以具有传递性。每个等价类就是一个强连通分量，简称 SCC。只有 a 能到 b 不够；无向并查集不能直接替代这个判定。

将每个 SCC 压成一个点，仅保留跨分量边，得到缩点图。它必然无环：若几个分量构成环，沿环就能相互到达，它们本应是同一个分量。

层次 能够忽略什么 仍要保留什么
分量内部 具体从哪个点进入，内部都能到达 点的费用、个数等权重
分量之间 同一方向的重复边通常不影响可达性 边的方向
DAG 上 不再需要处理有向环 源、汇、可达范围等全局关系

一个容易混淆的地方是：SCC 并不等于“度数大的一团点”，也不要求任意两点之间都有直接边。一条有向大环就是一个 SCC。

非递归 Kosaraju 为什么要记录退出顺序

Kosaraju 做两遍搜索。第一遍在原图建立完整 DFS 森林，在一个点的邻居全部处理完后，才把它加入退出序列。第二遍按退出序列的逆序，在反图中搜索，每次新搜索得到一个分量。

为什么方向恰好匹配？对缩点边 A → B，两分量不可能彼此可达。若先访问 A，搜索会完成 B 再完成 A；若先访问 B，B 无法进入 A，仍会先完成。因此 A 的最大退出时刻大于 B 的最大退出时刻。尚未分配的分量中，退出最晚者是原缩点图的源；转到反图后，它不会走进另一个尚未分配的分量。重复剥离便得到全部 SCC。

第一遍栈的状态 含义 何时改变
seen[v] v 是否已经入过栈 入栈时标记
next[v] 下一个待检查的邻居下标 每检查一条边就增加
st.back() 当前尚未退出的 DFS 节点 模拟递归调用栈
order 已完成节点的退出序列 邻居全部处理完才追加

例如只有 1 → 2 → 3 时，第一遍从 1 开始得到退出序列 [3,2,1]；反向处理 [1,2,3]，在反图中依次得到三个单点分量。如果误把入栈序列 [1,2,3] 当退出序列，反向从 3 搜索会把三个点错误合并。

第二遍只需收集反图可达的未分配点，不需要再记录退出时刻，可以用普通栈。以下三份实现都使用显式栈，避免十万点长链造成递归栈溢出；每个 SCC 对象只调用一次 build。

第一题 427C 每个分量选一个最低费用点

题目的保护关系要求双向可达：在 i 建检查站，能够保护 j 的条件是 i=j，或 i 能到 j 且 j 能到 i。于是一个站恰好能覆盖自身 SCC，不能覆盖其他 SCC。

先最小费用，再最少站点

每个分量至少需要一个站，而任意一个站都足够。因为费用非负，选最低费用点不会更差。特别注意：费用允许为 0。即使多个零费用站不增加总费用，题目还要求在最低费用下尽量少建站，因此仍然每个分量恰好选一个。

分量 点费用 最低贡献 可选最低费用点数
A 4、1、1 1 2
B 0、0 0 2
C 7 7 1
合并结果 各分量独立 8 2 × 2 × 1 = 4

正确性由两部分组成：任何方案在每个分量的花费都不小于分量最低费用；逐个选一个最低费用点达到该下界，且站点数也是必要的分量数。每个分量的选择互不限制，所以方案数相乘，对 1000000007 取模。

朴素方案 问题 SCC 后的处理
从每点分别搜索双向可达集合 可达性重复计算，最坏 O(n(n+m)) 两遍 DFS 一次划分
枚举所有站点子集 2ⁿ 个方案 每个分量扫描一次
只看最低费用不看站点数 多选零费用点导致多计方案 每个分量恰好一个站

总费用最大为 10⁵ × 10⁹ = 10¹⁴，不能使用 int。方案数的乘法中间值也使用 long long。

完整 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
#include <bits/stdc++.h>
using namespace std;

struct SCC {
    int n;
    vector<vector<int>> g, rg, groups;
    vector<int> comp;
    explicit SCC(int n_) : n(n_), g(n), rg(n), comp(n, -1) {}
    void add(int a, int b) { g[a].push_back(b); rg[b].push_back(a); }
    void build() {
        vector<char> seen(n, false);
        vector<size_t> next(n, 0);
        vector<int> order, st;
        for (int root = 0; root < n; ++root) {
            if (seen[root]) continue;
            seen[root] = true;
            st.push_back(root);
            while (!st.empty()) {
                int v = st.back();
                if (next[v] < g[v].size()) {
                    int u = g[v][next[v]++];
                    if (!seen[u]) { seen[u] = true; st.push_back(u); }
                } else {
                    order.push_back(v); // Exit time, not entry time.
                    st.pop_back();
                }
            }
        }
        for (auto it = order.rbegin(); it != order.rend(); ++it) {
            int root = *it;
            if (comp[root] != -1) continue;
            int id = static_cast<int>(groups.size());
            groups.push_back({});
            comp[root] = id;
            st.push_back(root);
            while (!st.empty()) {
                int v = st.back(); st.pop_back();
                groups[id].push_back(v);
                for (int u : rg[v]) if (comp[u] == -1) {
                    comp[u] = id; st.push_back(u);
                }
            }
        }
    }
};

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n; cin >> n;
    vector<long long> cost(n);
    for (auto &x : cost) cin >> x;
    SCC scc(n);
    int m; cin >> m;
    while (m--) { int a, b; cin >> a >> b; scc.add(a - 1, b - 1); }
    scc.build();
    const long long MOD = 1000000007;
    long long total = 0, ways = 1;
    for (const auto &group : scc.groups) {
        long long best = LLONG_MAX, count = 0;
        for (int v : group) {
            if (cost[v] < best) { best = cost[v]; count = 1; }
            else if (cost[v] == best) ++count;
        }
        total += best;
        ways = ways * count % MOD;
    }
    cout << total << ' ' << ways << '\n';
}

第二题 999E 未覆盖子图的源各需要一条新路

要求添加尽量少的有向边，使首都 s 能到达所有城市。先缩点，再从 s 所在分量搜索，将已经能到达的分量标记。剩下的分量诱导出一个 DAG，答案就是这个子图中入度为零的分量数。

为什么不数剩余城市或原图零入度点

假设首都已经覆盖 R，剩下 A、B、C、D，边为 A → C、B → C、C → D。给 A 和 B 各加一条从首都出发的边就足够，答案是 2，不是剩余分量数 4。

分量 未覆盖子图中的入边来源 是否需要直接接入
A 无 是
B 无 是
C A、B 否
D C 否

下界：每个未覆盖源都必须有新边进入，否则从首都无法第一次走入它。不同源不能共用同一条进入边，因此至少需要源的数量条边。注意原图不会存在“已覆盖分量 → 未覆盖分量”的边，否则后者早已被搜索覆盖。

上界：从首都分别连到每个未覆盖源。在有限 DAG 中，任一点都能沿入边反向追溯到一个源，因此这些新边能覆盖全部剩余分量。上下界相等，结论成立。

错误计数 反例
数未覆盖顶点 一个不可达的有向环只需要一条新路
数原图零入度顶点 上述环的每点入度都非零，仍需新路
数全部缩点图的源 首都已经覆盖的部分不应再次收费
数所有未覆盖分量 A → B → C 只需给 A 一条路

实现只记录 hasIn 布尔值，不必计算准确入度或给平行边去重。这里的 DAG 用于可达性与源判断，不需要真正运行拓扑排序。

完整 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
72
#include <bits/stdc++.h>
using namespace std;

struct SCC {
    int n;
    vector<vector<int>> g, rg, groups;
    vector<int> comp;
    explicit SCC(int n_) : n(n_), g(n), rg(n), comp(n, -1) {}
    void add(int a, int b) { g[a].push_back(b); rg[b].push_back(a); }
    void build() {
        vector<char> seen(n, false);
        vector<size_t> next(n, 0);
        vector<int> order, st;
        for (int root = 0; root < n; ++root) {
            if (seen[root]) continue;
            seen[root] = true;
            st.push_back(root);
            while (!st.empty()) {
                int v = st.back();
                if (next[v] < g[v].size()) {
                    int u = g[v][next[v]++];
                    if (!seen[u]) { seen[u] = true; st.push_back(u); }
                } else {
                    order.push_back(v); // Exit time, not entry time.
                    st.pop_back();
                }
            }
        }
        for (auto it = order.rbegin(); it != order.rend(); ++it) {
            int root = *it;
            if (comp[root] != -1) continue;
            int id = static_cast<int>(groups.size());
            groups.push_back({});
            comp[root] = id;
            st.push_back(root);
            while (!st.empty()) {
                int v = st.back(); st.pop_back();
                groups[id].push_back(v);
                for (int u : rg[v]) if (comp[u] == -1) {
                    comp[u] = id; st.push_back(u);
                }
            }
        }
    }
};

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, m, s; cin >> n >> m >> s; --s;
    SCC scc(n);
    while (m--) { int a, b; cin >> a >> b; scc.add(a - 1, b - 1); }
    scc.build();
    int k = static_cast<int>(scc.groups.size());
    vector<vector<int>> dag(k);
    for (int a = 0; a < n; ++a) for (int b : scc.g[a])
        if (scc.comp[a] != scc.comp[b])
            dag[scc.comp[a]].push_back(scc.comp[b]);
    vector<char> reached(k, false), hasIn(k, false);
    vector<int> st = {scc.comp[s]};
    reached[scc.comp[s]] = true;
    while (!st.empty()) {
        int a = st.back(); st.pop_back();
        for (int b : dag[a]) if (!reached[b]) {
            reached[b] = true; st.push_back(b);
        }
    }
    for (int a = 0; a < k; ++a) if (!reached[a])
        for (int b : dag[a]) if (!reached[b]) hasIn[b] = true;
    int answer = 0;
    for (int a = 0; a < k; ++a) if (!reached[a] && !hasIn[a]) ++answer;
    cout << answer << '\n';
}

第三题 949C 最小维护集合是一个汇分量

每个数据中心每天在小时 uᵢ 维护，时间按 h 小时循环。每位客户连接两个中心，初始两者的维护小时不同。现在要选择非空集合，将所选中心的维护时间都加一并对 h 取模，仍让每位客户的两个中心错开。目标是选择尽量少的中心。

从一次冲突推出边的方向

考虑客户连接 a、b。只有其中一个被选中时，才可能把原来不同的小时变成相同。

选择 a 选择 b 是否可能新冲突
否 否 不变，合法
是 是 同时循环平移，仍然不同
是 否 当 (uₐ+1) mod h = uᵦ 时冲突
否 是 当 (uᵦ+1) mod h = uₐ 时冲突

因此，如果 (uₐ+1) mod h = uᵦ，就建边 a → b，意思是“选择 a 必须选择 b”。反向条件同理。两个条件必须写成独立的 if：h=2 时它们能同时成立，不能用 else if 漏掉一个方向。

把每条边理解为蕴含关系后，合法选择集恰好是对后继封闭的非空集合：选一个点就必须选它能到达的所有点。一个 SCC 内的点必须同选或同不选。

最优性不只是“没有出边就合法”

一个汇分量没有跨分量出边，因此单独选择它确实合法。但合法还不等于最优，需要补上下界。

任取非空合法集合，从其中任一分量沿 DAG 出边不断向前。因为集合对后继封闭，经过的所有分量都在集合里；又因为 DAG 有限，最终到达整个缩点图的一个汇。该合法集合至少包含这个汇分量的全部点，其大小不小于“所有汇分量中的最小大小”。选最小汇恰好达到下界。

h 与小时 客户连接 蕴含图 最小合法选择
h=5，0、1、2 1—2、2—3 1 → 2 → 3 只选 3
h=2，0、1 1—2 1 ↔ 2 两点都选
h=3，0、1、2 1—2、2—3、3—1 三点成环 三点都选
h=5，4、0 1—2 1 → 2 只选 2

最后一行专门检查跨过午夜的取模。若存在孤立点，它自己就是大小 1 的汇分量，可以直接构成最优解。输入客户对重复只会产生重复蕴含边，不影响证明。

完整 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
#include <bits/stdc++.h>
using namespace std;

struct SCC {
    int n;
    vector<vector<int>> g, rg, groups;
    vector<int> comp;
    explicit SCC(int n_) : n(n_), g(n), rg(n), comp(n, -1) {}
    void add(int a, int b) { g[a].push_back(b); rg[b].push_back(a); }
    void build() {
        vector<char> seen(n, false);
        vector<size_t> next(n, 0);
        vector<int> order, st;
        for (int root = 0; root < n; ++root) {
            if (seen[root]) continue;
            seen[root] = true;
            st.push_back(root);
            while (!st.empty()) {
                int v = st.back();
                if (next[v] < g[v].size()) {
                    int u = g[v][next[v]++];
                    if (!seen[u]) { seen[u] = true; st.push_back(u); }
                } else {
                    order.push_back(v); // Exit time, not entry time.
                    st.pop_back();
                }
            }
        }
        for (auto it = order.rbegin(); it != order.rend(); ++it) {
            int root = *it;
            if (comp[root] != -1) continue;
            int id = static_cast<int>(groups.size());
            groups.push_back({});
            comp[root] = id;
            st.push_back(root);
            while (!st.empty()) {
                int v = st.back(); st.pop_back();
                groups[id].push_back(v);
                for (int u : rg[v]) if (comp[u] == -1) {
                    comp[u] = id; st.push_back(u);
                }
            }
        }
    }
};

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, m, h; cin >> n >> m >> h;
    vector<int> hour(n);
    for (int &x : hour) cin >> x;
    SCC scc(n);
    while (m--) {
        int a, b; cin >> a >> b; --a; --b;
        if ((hour[a] + 1) % h == hour[b]) scc.add(a, b);
        if ((hour[b] + 1) % h == hour[a]) scc.add(b, a);
    }
    scc.build();
    int k = static_cast<int>(scc.groups.size());
    vector<char> hasOut(k, false);
    for (int a = 0; a < n; ++a) for (int b : scc.g[a])
        if (scc.comp[a] != scc.comp[b]) hasOut[scc.comp[a]] = true;
    int best = -1;
    for (int c = 0; c < k; ++c) if (!hasOut[c]) {
        if (best == -1 || scc.groups[c].size() < scc.groups[best].size()) best = c;
    }
    cout << scc.groups[best].size() << '\n';
    for (int v : scc.groups[best]) cout << v + 1 << ' ';
    cout << '\n';
}

复杂度与实现边界

部分 时间 额外空间 需要留意
非递归 Kosaraju O(n+m) O(n+m) 原图、反图和显式 DFS 栈
427C 分量统计 O(n) O(n) 费用与乘法使用 64 位
999E 缩点与覆盖 O(n+m) O(n+m) 仅统计未覆盖部分的入边
949C 蕴含图与汇判断 O(n+m) O(n+m) 每个客户至多生成两条边

表中 949C 的 m 指客户数，最多 2m 条有向蕴含边；常数变化不改变线性复杂度。算法线性不代表可以忽略语言、内存分配与评测机差异，本地运行不等于官方提交通过。

错误清单 修正
只从节点 1 开始第一遍 DFS 必须遍历所有未访问根，覆盖非连通部分
第一遍记录入栈顺序 保存所有邻居处理完后的退出顺序
第二遍仍用原图 必须在反图搜索
十万点链使用未经评估的递归 显式栈模拟退出过程
把分量编号当可靠业务顺序 按实际跨分量边判断入度、出度
949C 随便取最小 SCC 必须在汇分量中取最小，否则会牵连外部
949C 忘记非空限制 输出至少一个点，空集合不是答案
427C 将零费用点随意多选 最低费用之下还需最少站点数

用独立方法验证而不是复写同一模板

验证脚本为 tests/verify-scc-three-article.cjs，提取本文三份代码直接编译。小数据基准不调用 SCC：427C 用传递闭包和所有站点子集检查费用、站点数及方案数；999E 枚举从首都补边的目标集合并做 BFS；949C 枚举非空集合，实际平移小时并逐客户检查冲突。

999E 的基准为何可以只枚举首都出发的边？对任意可行补边方案，把每条新边 a → b 改为 s → b，原来沿新边到达 b 的能力不会减弱；之后的旧边路径仍然可走。因此总有同样数量以内的首都出边方案，不会漏掉更优解。这个基准虽慢，却不依赖缩点或源数量定理。

此外覆盖空图、全零费用、长链、整图一个 SCC、重复客户、h=2 双向蕴含、循环边界和最大规模。验证只说明这些测试范围内与独立基准一致，不替代正确性证明。

本轮三份 C++17 均无警告编译，共通过 1,166 次执行与 31,880 个独立子集核验；小数据包含 199 张有向图和 550 组维护安排，另有官方样例及十万点、三十万条边等边界测试。

下一步怎样串回路线

先把 拓扑排序三题里的 DAG 依赖关系重新看一遍，再问“如果出现环，环代表矛盾还是一个必须整体处理的集合”。随后比较 并查集三题：并查集合并的是无向连通性，而 SCC 利用的是有向双向可达，两者不能混用。

本篇最值得保留的不是模板名字，而是三个不同的问题出口：分量内部做统计、未覆盖子图找源、后继封闭集合找汇。返回算法路线可以按图论与树上查询继续练习。