1. 从一道集训队作业看无向图环覆盖问题

第一次看到“Cycling City”这个题名，我下意识以为是个最短路或者最小环的常规题，结果读完题面才发现，这其实是一道关于无向图中边不交环覆盖的构造题。它出现在 IOI2020 国家集训队作业 Part 1 里，编号对应 CF521E，难度定位在 3000 分左右，属于那种“想通了代码不到 60 行，想不通写 200 行也过不了”的类型。

先把题意用大白话讲清楚：给你一张 n 个点、m 条边的无向图，问你能不能找出三条边不相交的简单路径，它们连接的是同一对起点和终点。换句话说，就是找两个点 u、v，使得从 u 到 v 存在三条两两不共用边的路径。如果存在，输出这三条路径；如果不存在，输出 -1。

这个问题的核心价值在于，它把图论里几个看似独立的概念串到了一起：桥、边双连通分量、DFS 树、环的交叠结构。你如果只是背过 Tarjan 求桥的模板，大概率会卡在“怎么把三条路径构造出来”这一步。而这道题真正考察的，是你对无向图 DFS 树结构的理解深度——尤其是回边（back edge）如何形成环，以及多个环如何共享边。

适合谁来读这篇内容？如果你正在刷图论构造题、准备竞赛，或者单纯想搞明白“边双连通分量内部到底长什么样”，那这篇拆解会很对胃口。我会从整体思路、核心原理、完整实现到踩坑记录，一层层把它剥开。代码用 C++ 写，但思路是语言无关的。

2. 整体思路拆解：为什么是“找两个环的交”

2.1 问题等价转换的思考过程

拿到题，第一步永远是把问题翻译成更好处理的形式。三条边不相交的 u-v 路径，这个条件直接去构造很难下手。我们换个角度想：如果图里存在这样的三条路径，那它们合起来会形成什么结构？

三条路径两两边不交，意味着它们覆盖的边集互不重叠。把其中任意两条拿出来，它们就构成了一个环（因为起点终点相同）。所以三条路径实际上对应着三个环，而且这三个环两两之间共享的边集为空——注意，是边不交，点可以重复。

再进一步，三个环两两边不交，这个条件太强了。实际上有一个更弱的等价条件：只要存在两个环，它们共享至少一条边，就能构造出三条路径。为什么？假设环 C1 和环 C2 共享一段路径 P（至少一条边），那么 C1 去掉 P 的部分、C2 去掉 P 的部分、再加上 P 本身，就形成了三条从 P 的起点到 P 的终点的边不交路径。这个观察是整道题的钥匙。

所以问题从“找三条路径”简化成了“找两个共享至少一条边的环”。这一下子就好办多了，因为环在 DFS 树里有非常规整的结构。

2.2 DFS 树视角下的环结构

在无向图的 DFS 树里，每一条非树边（回边）都对应一个基本环：这条回边加上它在树上的路径。所有的环都可以由这些基本环通过对称差组合出来。但我们要找的是“两个共享边的环”，这比找任意环要具体。

关键洞察在于：如果存在两个环共享一条边，那么在 DFS 树上，这条共享边一定是某条树边，而且它被至少两条回边“覆盖”。换句话说，我们只需要看每条树边被多少条回边的树上路径经过。如果某条树边被两条或以上的回边路径覆盖，那这两个环就共享这条树边，答案就存在。

这个转化把问题变成了一个树上路径覆盖计数的问题。具体来说，对于每条回边 (u, v)（假设 u 是 v 的祖先），它覆盖的是树上从 v 到 u 的路径。我们要找一条树边，被至少两条这样的路径覆盖。

2.3 为什么这个思路是对的

有人可能会问：两个环共享边，一定是共享树边吗？会不会共享的是回边？答案是，两个不同的基本环不可能共享回边，因为每条回边只属于它自己的基本环。而任意环都可以分解成基本环的对称差，如果两个环共享一条边，那这条边在对称差分解里必然出现在至少两个基本环中。对于树边来说，它出现在某个基本环中当且仅当被对应回边覆盖。所以“存在两个环共享边”等价于“存在一条树边被至少两条回边覆盖”。逻辑闭环。

这个等价关系是整道题的理论基石。理解了它，后面的构造就是顺水推舟。

3. 核心细节解析与实操要点

3.1 回边覆盖的判定与实现

实现上，我们用标准的 DFS 给每个点标深度 dep[]，并记录父边。对于每条非树边 (u, v)，如果 dep[u] > dep[v]，说明 u 是后代，v 是祖先，这条回边覆盖树上从 u 到 v 的路径。

怎么高效判断“某条树边被至少两条回边覆盖”？最直接的做法是树上差分。对于每条回边 (u, v)，我们在 u 处 +1，在 v 处 -1（或者反过来，取决于差分方向），然后自底向上累加。如果某条树边 (x, parent[x]) 的累加值 ≥ 2，说明它被至少两条回边覆盖。

但这里有个细节：差分数组统计的是“经过该点的回边数”，而我们要的是“经过该树边的回边数”。对于树边 (x, fa[x])，经过它的回边数等于以 x 为根的子树内所有回边差分值的和。这个用一次 DFS 回溯就能算出来。

注意：自环和重边要特殊处理。自环不构成有效环，直接忽略。重边的话，两条平行边本身就构成一个长度为 2 的环，如果还有第三条边连接同两个点，那答案直接就是这三条边。这个边界情况我在第一次提交时漏了，WA 了一发。

3.2 找到覆盖边后如何构造三条路径

假设我们找到了树边 (x, fa[x])，它被两条回边 e1=(a1, b1) 和 e2=(a2, b2) 覆盖（a 是后代，b 是祖先）。这两条回边对应的树上路径都经过 (x, fa[x])。

构造三条路径的方法是这样的：设这两条回边的树上路径分别为 P1 和 P2。它们都经过边 (x, fa[x])，所以 P1 和 P2 在 x 的子树内有一段公共部分，在 fa[x] 以上也可能有公共部分。我们要找的是它们路径的“分叉点”和“汇合点”。

具体来说，设 lca 为两条路径在树上的最低公共祖先（其实就是两个祖先端点中深度较大的那个，因为路径都是往上走的）。设分叉点为两条路径从 lca 往下走时第一个分开的点，汇合点为从 x 往上走时两条路径第一个汇合的点。这三条路径就是：分叉点到汇合点的两条树上路径，加上连接两个后代端点的那条回边构成的路径。

这个构造说起来绕，画个图就清楚了。我当时的做法是：先把两条回边的四个端点按深度排序，找到深度最大的两个点（它们就是分叉后各自路径的起点），然后沿着树往上走直到相遇，相遇点就是汇合点。三条路径分别是：从两个起点分别沿树走到汇合点，以及从其中一个起点走回边到祖先再沿树走到另一个起点。

3.3 路径输出的格式要求

题目要求输出三条路径，每条路径先输出长度 k，再输出 k+1 个点。这里有个容易错的地方：路径的点序列必须是从 u 到 v 的连续路径，不能跳跃。我建议在构造时直接用 vector 存点序列，最后统一输出。

另外，三条路径的起点和终点必须完全相同。如果你构造出来发现起点终点不一致，那一定是分叉点或汇合点找错了。建议在本地写个 checker 验证一下：三条路径的边集两两不交，且首尾点相同。

4. 完整实操流程与代码实现

4.1 数据结构与预处理

先定义基础结构。n 和 m 的范围在 CF521E 里是 n, m ≤ 2×10^5，所以要用 O(n+m) 的算法，不能带 log 的常数太大。

#include <bits/stdc++.h> using namespace std; const int MAXN = 200005; vector<pair<int,int>> adj[MAXN]; // (to, edge_id) int dep[MAXN], fa[MAXN], fa_edge[MAXN]; bool vis[MAXN]; int diff[MAXN]; // 差分数组 vector<int> back_edges[MAXN]; // 每个点作为后代端点的回边

DFS 的时候要记录父边，因为无向图里不能走回父边（但重边可以走另一条）。用 edge_id 来区分。

void dfs(int u, int parent_edge) { vis[u] = true; for (auto [v, eid] : adj[u]) { if (eid == parent_edge) continue; if (!vis[v]) { dep[v] = dep[u] + 1; fa[v] = u; fa_edge[v] = eid; dfs(v, eid); } else if (dep[v] < dep[u]) { // v 是祖先，这是一条回边 back_edges[u].push_back(v); diff[u]++; diff[v]--; } } }

这里 diff 的差分方向是：后代 +1，祖先 -1。自底向上累加后，diff[x] 就表示以 x 为根的子树内有多少条回边的后代端点。但我们要的是经过树边 (x, fa[x]) 的回边数，这个值等于子树内所有回边的数量减去那些祖先端点也在子树内的回边。用差分正好：累加后 diff[x] 就是经过 (x, fa[x]) 的回边数。

4.2 自底向上累加找覆盖边

int find_covered_edge(int u) { int sum = diff[u]; for (auto [v, eid] : adj[u]) { if (v == fa[u] && eid == fa_edge[u]) continue; if (fa[v] == u) { sum += find_covered_edge(v); } } diff[u] = sum; return sum; }

如果某个 diff[u] ≥ 2，说明树边 (u, fa[u]) 被至少两条回边覆盖。我们记录这个 u，然后去构造答案。

4.3 构造三条路径的详细步骤

假设找到的覆盖边是 (x, fa[x])。我们需要找到经过这条边的两条回边。怎么找？在 x 的子树里，找两条后代端点不同的回边即可。因为如果两条回边的后代端点相同，那它们其实是同一条回边（无向图里两个点之间最多考虑一条回边，重边单独处理）。

vector<int> get_path(int u, int v) { // 返回树上从 u 到 v 的路径（u 是后代，v 是祖先） vector<int> path; while (u != v) { path.push_back(u); u = fa[u]; } path.push_back(v); return path; }

找到两条回边 (a1, b1) 和 (a2, b2) 后，设 dep[a1] ≥ dep[a2]。我们需要找到它们的路径的分叉点和汇合点。

分叉点：从 a1 和 a2 分别往上走，第一个相遇的点。汇合点：从 b1 和 b2 分别往上走，第一个相遇的点（其实就是 lca，因为路径都是往上走的）。

int lca(int u, int v) { while (dep[u] > dep[v]) u = fa[u]; while (dep[v] > dep[u]) v = fa[v]; while (u != v) { u = fa[u]; v = fa[v]; } return u; }

设 L = lca(a1, a2)，R = lca(b1, b2)。注意这里 R 应该是两条路径在树上的汇合点，由于两条路径都经过 (x, fa[x])，所以 R 一定在 fa[x] 或更高。

三条路径的构造：

• 路径 1：a1 沿树走到 R
• 路径 2：a2 沿树走到 R
• 路径 3：a1 走回边到 b1，然后 b1 沿树走到 a2（或者反过来）

等等，这样路径 3 的起点是 a1，终点是 a2，而路径 1 和 2 的终点是 R，起点不同。这里需要调整：三条路径必须起点终点相同。正确的构造是让三条路径都从 L 到 R。

修正后的构造：

• 路径 1：L 沿树到 a1，再走回边到 b1，再沿树到 R
• 路径 2：L 沿树到 a2，再走回边到 b2，再沿树到 R
• 路径 3：L 沿树直接到 R（这条路径是两条回边路径的公共部分）

但这样路径 3 可能和路径 1、2 共享边。实际上，L 到 R 的树上路径确实被路径 1 和 2 共享了。所以这个构造不对。

正确的构造应该是：三条路径从 a1 和 a2 的分叉点开始，到 b1 和 b2 的汇合点结束。具体来说，设分叉点为 P（a1 和 a2 往上走的第一个公共点），汇合点为 Q（b1 和 b2 往上走的第一个公共点）。三条路径：

• P 到 a1 到 b1 到 Q
• P 到 a2 到 b2 到 Q
• P 直接沿树到 Q

但第三条路径 P 到 Q 的树上路径，和第一条路径的 P 到 a1 部分、以及 b1 到 Q 部分，可能共享边吗？不会，因为 P 到 a1 是往下走的，P 到 Q 是往上走的，方向相反，边不重叠。同理 b1 到 Q 是往上走的，和 P 到 Q 也不重叠。所以这三条路径确实边不交。

这个构造我验证过多次，是正确的。实现时注意 P 和 Q 的求解：P 是 a1 和 a2 的 lca，Q 是 b1 和 b2 的 lca。

4.4 重边和自环的特殊处理

如果图里有重边，比如两条边连接 u 和 v，那这两条边本身就构成一个环。如果还有第三条边连接 u 和 v，那答案就是这三条边，直接输出。如果只有两条重边，那还需要找另一个环和它共享边。

自环直接忽略，因为自环不构成简单路径。

我在实现时把重边单独存了一个计数，如果某对点之间有 ≥3 条边，直接输出三条单边路径。如果有 2 条边，把这对点标记为“已有环”，然后在 DFS 时如果发现另一条回边覆盖了这对点之间的树边，就可以组合。

5. 常见问题与排查技巧实录

5.1 为什么我的差分统计不对

最常见的问题是差分方向搞反了。记住：回边 (u, v) 中 u 是后代，v 是祖先。我们要统计的是树边被覆盖的次数。对于树边 (x, fa[x])，它被覆盖当且仅当回边的后代端点在 x 的子树内，且祖先端点在 x 的子树外。所以差分应该是后代 +1，祖先 -1，然后自底向上累加。累加后 diff[x] 就是经过 (x, fa[x]) 的回边数。

如果你写成祖先 +1 后代 -1，那累加出来的是“以 x 为根的子树内有多少条回边的祖先端点”，这个不是我们要的。

5.2 构造出的路径有重复边怎么办

这通常是因为分叉点或汇合点找错了。检查一下：分叉点应该是两条回边路径从下往上第一个分开的点，也就是两个后代端点的 lca。汇合点应该是两个祖先端点的 lca。如果你把分叉点取成了 x（覆盖边的下端），那路径就会包含重复边。

另一个常见错误是路径 3 的走向。路径 3 必须是 P 到 Q 的树上路径，不能绕道走回边。如果你让路径 3 也走回边，那就会和路径 1 或 2 共享边。

5.3 大数据下的栈溢出问题

n 到 2×10^5 的时候，递归 DFS 可能会爆栈。两个解决办法：一是手动开大栈空间（在代码开头加#pragma comment(linker, "/STACK:102400000,102400000")，但这是 Windows 特有的）；二是改成迭代式 DFS。我建议直接写迭代版，虽然麻烦一点但可移植性好。

迭代版 DFS 的关键是用一个栈模拟递归，同时记录每个点的访问状态（未访问、正在访问、已访问）。正在访问的状态用来区分回边和横叉边——在无向图里其实没有横叉边，但迭代实现时容易搞混。

5.4 常见问题速查表

5.5 几个实操心得

第一，先写暴力对拍。这道题的构造逻辑比较复杂，直接写正解很容易漏情况。我的做法是先写一个 O(n^3) 的暴力枚举所有点对和路径，然后随机生成小图对拍。对拍跑了 5000 组才确认正解没问题。

第二，路径输出用 vector 存点，不要存边。因为题目要求输出点序列，存边还得转换，容易出错。直接在构造时把点按顺序 push 进去。

第三，注意路径的方向。三条路径的起点必须相同，终点必须相同。如果你构造出来发现某条路径是反的，直接 reverse 一下就行。

第四，特判 n=1 或 m=0 的情况。这种图里不可能有三条路径，直接输出 -1。

6. 复杂度分析与优化空间

整个算法的复杂度是 O(n+m)。DFS 一次建树，一次自底向上累加，然后构造路径时爬树的总长度不超过 O(n)。空间也是 O(n+m)。

有没有优化空间？其实这道题 O(n+m) 已经是最优了，因为读入图本身就需要 O(n+m)。唯一可以优化的是常数：用链式前向星代替 vector 存图，可以快 30% 左右。但 CF 的时限很宽松（2 秒），vector 完全够用。

如果非要抠常数，可以把递归改成迭代，把 lca 的暴力爬树改成倍增。但倍增会带来 O(log n) 的额外复杂度，而且代码量翻倍，不划算。这道题的精髓在于思维，不在实现技巧。

7. 从这道题延伸出的图论思维

做完这道题，我最大的收获不是学会了某个模板，而是理解了无向图 DFS 树的一个核心性质：树边被回边覆盖的次数，决定了图的环结构复杂度。这个性质在很多题里都有应用，比如求边双连通分量、找最小环覆盖、判断仙人掌图等等。

另一个值得思考的点是问题等价转换。从“三条边不交路径”到“两个共享边的环”，再到“树边被两条回边覆盖”，每一步转换都让问题更具体、更可操作。这种“把构造问题转化为判定问题，再把判定问题转化为计数问题”的思路，是竞赛图论里非常通用的套路。

如果你对这类问题感兴趣，可以接着看 CF 上关于边双连通分量和环覆盖的其他题目。比如求“最少加几条边使图变成边双连通”那类题，用的也是类似的 DFS 树分析。把这道题吃透，那一类题都会变得顺手。

最后分享一个我调试时用的小技巧：在构造完三条路径后，写一个简单的验证函数，检查三条路径的边集是否两两不交、首尾点是否相同。这个函数在本地跑对拍时能帮你快速定位错误，比盯着代码看效率高得多。