找环之前,先明确需要什么结果:判断是否有环、找一条环边,还是按顺序列出一个环上的点和边。它们需要保留的信息不同。
本文的环不重复经过顶点,末尾回到起点;允许自环作为长度为
| 任务 | 方法 | 结果 |
|---|---|---|
| 无向图判环或找一条环边 | 并查集 | 一条使合并失败的原图边 |
| 无向图恢复任意一个环 | DFS | 环的点序、边序 |
| 基环树找出唯一的环 | 剥叶法 | 全部环上点,再沿环恢复顺序 |
| 有向图恢复任意一个环 | 三色 DFS | 按方向排列的点序、边序 |
一般图可能有很多环,本篇的恢复模板找到一个就停止。基环树恰好只有一个环,因此找到的就是它的全部环上点和边。结构与后续算法见 基环树。
1 并查集找环边
依次读入无向边
- 两端不连通:合并两个集合,保留这条边。
- 两端已经连通:保留的边中已经存在
到 的路径,再加上当前边就形成环。
成功合并的边始终构成森林,因此它们之间的路径唯一。合并失败的这条原图边,一定在某个环上。
设 unite(u, v) 在 true,已经连通时返回 false,核心循环只需判断合并是否失败:
for (int id = 1; id <= m; ++id) {
int u, v;
cin >> u >> v;
if (!unite(u, v) && answer == 0) {
answer = id, from = u, to = v; // 两端已连通,记录第一条环边
}
}
沿用草稿的五点例子,边按如下顺序输入:
5 5
1 4
1 2
2 3
3 4
2 5
前三条边已形成路径
1.1 基环树断边
基环树是连通且恰好含一个环的无向图,等价于一棵树增加一条边,因而有
处理完基环树的全部边,恰有一次合并失败:保留的
这适合只需要断开一条环边、再运行树上算法的题目。它不一定是输入的最后一条边;改变输入顺序,也可能选中环上的另一条边。在一般多环图中,删除一条这样的边后还可能有环。
模板输入格式如上,边编号为输入行的顺序,从 编号 u v,无环输出 0。样例输出为 4 3 4。
完整代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200000 + 5;
int n, m, fa[maxn], sz[maxn];
int find(int x) {
if (fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
bool unite(int x, int y) {
int fx = find(x), fy = find(y);
if (fx == fy) return false;
if (sz[fx] < sz[fy]) swap(fx, fy);
fa[fy] = fx;
sz[fx] += sz[fy];
return true;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (!(cin >> n >> m)) return 0;
for (int u = 1; u <= n; ++u) {
fa[u] = u;
sz[u] = 1;
}
int answer = 0, from = 0, to = 0;
for (int id = 1; id <= m; ++id) {
int u, v;
cin >> u >> v;
if (!unite(u, v) && answer == 0) {
// 两端已经连通,记录第一条使合并失败的原图边。
answer = id;
from = u;
to = v;
}
}
if (answer == 0) cout << 0 << '\n';
else cout << answer << ' ' << from << ' ' << to << '\n';
return 0;
}
采用路径压缩与按大小合并,时间复杂度为
1.2 从一条边恢复环
如果还需要整个环,可以在成功合并时,额外将这条原图边存入邻接表。找到失败边
完整代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200000 + 5;
struct Edge { int to, id; };
int n, m;
int fa[maxn], sz[maxn];
vector<Edge> g[maxn]; // 另存森林边;不能沿并查集 fa 恢复原图路径
int parent[maxn], parent_edge[maxn]; // 记录 BFS 路径上的父节点与来边编号
bool vis[maxn];
vector<int> cycle_v, cycle_e;
int find(int x) {
if (fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
bool unite(int x, int y) {
int fx = find(x), fy = find(y);
if (fx == fy) return false;
if (sz[fx] < sz[fy]) swap(fx, fy);
fa[fy] = fx;
sz[fx] += sz[fy];
return true;
}
void recover_cycle(int from, int to, int fail_id) {
queue<int> q;
q.push(from);
vis[from] = true;
while (!q.empty()) {
int x = q.front();
q.pop();
if (x == to) break; // 森林中路径唯一,到达 to 即可结束
for (Edge e : g[x]) {
if (vis[e.to]) continue;
vis[e.to] = true;
parent[e.to] = x;
parent_edge[e.to] = e.id;
q.push(e.to);
}
}
// 沿着 parent 从 to 回到 from,最后补上失败边闭合环(自环同样适用)。
for (int x = to; x != from; x = parent[x]) {
cycle_v.push_back(x);
cycle_e.push_back(parent_edge[x]);
}
cycle_v.push_back(from);
cycle_e.push_back(fail_id);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (!(cin >> n >> m)) return 0;
for (int u = 1; u <= n; ++u) {
fa[u] = u;
sz[u] = 1;
}
int fail_id = 0, from = 0, to = 0;
for (int id = 1; id <= m; ++id) {
int u, v;
cin >> u >> v;
if (unite(u, v)) {
// 合并成功:加入森林,供后续恢复路径使用
g[u].push_back({v, id});
g[v].push_back({u, id});
} else if (fail_id == 0) {
// 两端已连通:只记录第一条使合并失败的环边
fail_id = id;
from = u;
to = v;
}
}
if (fail_id == 0) {
cout << 0 << '\n';
return 0;
}
recover_cycle(from, to, fail_id);
cout << cycle_v.size() << '\n';
for (auto i : cycle_v) cout << i << ' ';
cout << '\n';
for (auto i : cycle_e) cout << i << ' ';
cout << '\n';
return 0;
}
不能直接沿并查集的 fa 数组恢复路径。 并查集的父子关系用于维护集合,可能经过路径压缩,并不对应原图中的边。恢复原图路径需要另存的森林。
2 DFS 恢复环
无向图 DFS 首次发现一个点时,记录它的父亲 parent[v] 和进入它的边号 parent_edge[v],这些边构成 DFS 森林。
检查当前点
图中 DFS 路径为
2.1 时间戳与来边
令 dfn[u] 为首次访问时间。无向图 DFS 的非树边连接祖先与后代,因此只在 dfn[v] < dfn[u] 时,从后代向祖先恢复环;另一侧会看到较大的时间戳,不必再处理。自环单独用 v == u 识别。
同一条无向边在两端邻接表中共用一个编号。跳过来边应写成:
if (e.id == parent_edge[u]) continue;
不能跳过所有指向父亲顶点的边。如果父子之间有两条不同边,进入当前点的那条要跳过,另一条却恰好能构成长为
2.2 恢复点序与边序
沿 parent 从 parent_edge;最后补上回边
三份恢复模板统一输出:第一行环长 cycle_e[i] 连接 cycle_v[i] 与 cycle_v[(i+1)%k],末尾不重复输出起点;没有环时只输出 0。
无向 DFS 还会设置 on_vertex、on_edge,标记本次找到的这个环,不是一般图中所有环的并集。
完整代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200000 + 5;
const int maxm = 400000 + 5;
struct Edge { int to, id; };
int n, m, timer;
vector<Edge> g[maxn];
int dfn[maxn], parent[maxn], parent_edge[maxn];
int next_edge[maxn], st[maxn];
int len, cycle_v[maxn], cycle_e[maxn];
bool on_vertex[maxn], on_edge[maxm];
void build_cycle(int u, int v, int back_id) {
// v 是祖先(自环时 u == v),先得到 u 到 v 的逆序点列。
for (int x = u; x != v; x = parent[x]) cycle_v[len++] = x;
cycle_v[len++] = v;
reverse(cycle_v, cycle_v + len);
for (int i = 0; i + 1 < len; ++i) {
cycle_e[i] = parent_edge[cycle_v[i + 1]];
}
cycle_e[len - 1] = back_id; // 最后一条边从 u 闭合到 v
for (int i = 0; i < len; ++i) {
on_vertex[cycle_v[i]] = true;
on_edge[cycle_e[i]] = true;
}
}
bool dfs(int s) {
int top = 0;
dfn[s] = ++timer;
st[top++] = s;
while (top > 0) {
int u = st[top - 1];
if (next_edge[u] == (int)g[u].size()) {
--top; // 所有邻边已处理,模拟递归返回
continue;
}
Edge e = g[u][next_edge[u]++];
if (e.id == parent_edge[u]) continue; // 只跳过进入 u 的那条边
int v = e.to;
if (dfn[v] == 0) {
parent[v] = u;
parent_edge[v] = e.id;
dfn[v] = ++timer;
st[top++] = v;
} else if (v == u || dfn[v] < dfn[u]) {
build_cycle(u, v, e.id);
return true; // 只恢复一个环,找到后立即结束
}
}
return false;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (!(cin >> n >> m)) return 0;
for (int id = 1; id <= m; ++id) {
int u, v;
cin >> u >> v;
g[u].push_back({v, id});
g[v].push_back({u, id});
}
for (int u = 1; u <= n; ++u) {
if (dfn[u] == 0 && dfs(u)) break;
}
cout << len << '\n';
if (len == 0) return 0;
for (int i = 0; i < len; ++i) cout << cycle_v[i] << ' ';
cout << '\n';
for (int i = 0; i < len; ++i) cout << cycle_e[i] << ' ';
cout << '\n';
return 0;
}
代码用 st 模拟递归路径,next_edge[u] 记录返回
每条边至多检查两次,找到环后只回溯一次,时间复杂度为
3 基环树剥叶
如果已知图是基环树,可以不断删除度数为
环上每个点都有两条环边,不会被删成叶子;环外是一棵棵挂树,最外层叶子删除后,内部节点会逐渐成为新叶子。最终恰好留下唯一的环。前面的五点图只需删除点
用队列维护待删除点。删掉一个点时,将尚未删除邻点的度数减一,度数降到
剥叶只能确定剩余的点集,不能得到环序。在基环树中,剩下每个点的度数恰好为
完整代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200000 + 5;
struct Edge { int to, id; };
int n, m, deg[maxn], q[maxn];
vector<Edge> g[maxn];
bool in_cycle[maxn];
int len, cycle_v[maxn], cycle_e[maxn];
void peel() {
int head = 0, tail = 0;
for (int u = 1; u <= n; ++u) {
in_cycle[u] = true;
if (deg[u] <= 1) q[tail++] = u;
}
while (head < tail) {
int u = q[head++];
in_cycle[u] = false;
for (Edge e : g[u]) {
int v = e.to;
if (!in_cycle[v]) continue;
if (--deg[v] == 1) q[tail++] = v;
}
}
}
void walk_cycle(int start) {
int u = start, in_edge = 0;
do {
cycle_v[len] = u;
for (Edge e : g[u]) {
if (!in_cycle[e.to] || e.id == in_edge) continue;
cycle_e[len++] = e.id;
in_edge = e.id;
u = e.to;
break;
}
} while (u != start);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
// 本模板用于连通基环树;沿环走一圈依赖这个前提。
if (!(cin >> n >> m)) return 0;
for (int id = 1; id <= m; ++id) {
int u, v;
cin >> u >> v;
g[u].push_back({v, id});
g[v].push_back({u, id});
++deg[u];
++deg[v]; // 自环对度数贡献 2
}
peel();
for (int u = 1; u <= n; ++u) {
if (in_cycle[u]) {
walk_cycle(u);
break;
}
}
cout << len << '\n';
if (len == 0) return 0;
for (int i = 0; i < len; ++i) cout << cycle_v[i] << ' ';
cout << '\n';
for (int i = 0; i < len; ++i) cout << cycle_e[i] << ' ';
cout << '\n';
return 0;
}
输入为连通基环树,
3.1 一般图的限制
一般无向图反复删除度数不超过
图中点
若已知每个连通块至多一个环,剥叶后确实只剩各个环,但还需要逐个分组、分别绕行。上面的单环模板只输出其中一个,不能直接当作所有环的枚举器。
4 有向图找环
有向图的边有方向,不能直接使用普通并查集判定有向环。例如
DFS 时也不能将“到达已访问点”等同于“发现环”。同一个例子中,先搜索完点
需要区分三种状态:
color |
含义 |
|---|---|
| 尚未访问 | |
| 已进入,仍在当前 DFS 路径上 | |
| 邻边全部检查完毕,已退出当前路径 |
从 color[v] == 1,树上已有有向路径
恢复方式仍是沿父亲回溯,再反转点列,边序必须与方向一致。有向图不跳过指向父亲的边:父亲到孩子的树边与孩子返回父亲的边,已经构成一个有向环。
完整代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200000 + 5;
struct Edge { int to, id; };
int n, m;
vector<Edge> g[maxn];
int color[maxn], parent[maxn], parent_edge[maxn];
int next_edge[maxn], st[maxn];
int len, cycle_v[maxn], cycle_e[maxn];
void build_cycle(int u, int v, int back_id) {
for (int x = u; x != v; x = parent[x]) cycle_v[len++] = x;
cycle_v[len++] = v;
reverse(cycle_v, cycle_v + len);
for (int i = 0; i + 1 < len; ++i) {
cycle_e[i] = parent_edge[cycle_v[i + 1]];
}
cycle_e[len - 1] = back_id;
}
bool dfs(int s) {
int top = 0;
color[s] = 1;
st[top++] = s;
while (top > 0) {
int u = st[top - 1];
if (next_edge[u] == (int)g[u].size()) {
color[u] = 2; // 退出当前 DFS 路径
--top;
continue;
}
Edge e = g[u][next_edge[u]++];
int v = e.to;
if (color[v] == 0) {
parent[v] = u;
parent_edge[v] = e.id;
color[v] = 1;
st[top++] = v;
} else if (color[v] == 1) {
// v 仍在当前路径上,树路径 v -> ... -> u 与 u -> v 闭合。
build_cycle(u, v, e.id);
return true;
}
// 指向 color == 2 的点不能据此判环;有向图不跳过“父亲边”。
}
return false;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (!(cin >> n >> m)) return 0;
for (int id = 1; id <= m; ++id) {
int u, v;
cin >> u >> v;
g[u].push_back({v, id}); // 有向边只存一次
}
for (int u = 1; u <= n; ++u) {
if (color[u] == 0 && dfs(u)) break;
}
cout << len << '\n';
if (len == 0) return 0;
for (int i = 0; i < len; ++i) cout << cycle_v[i] << ' ';
cout << '\n';
for (int i = 0; i < len; ++i) cout << cycle_e[i] << ' ';
cout << '\n';
return 0;
}
模板按有向边读入,每条边只存一次,使用显式栈并遍历所有连通部分。输出约定与前面的恢复模板一致,但每条边必须沿输入方向连接相邻点。时间和空间复杂度均为
如果只需判断有向图是否有环,也可以用 拓扑排序:无法输出全部顶点就说明存在环。不过一般有向图中,Kahn 算法留下的顶点可能包含环的后继,不能直接当作环上点。
本文模板按
5 相关题解
暂无相关题解