找环

找环之前,先明确需要什么结果:判断是否有环、找一条环边,还是按顺序列出一个环上的点和边。它们需要保留的信息不同。

本文的环不重复经过顶点,末尾回到起点;允许自环作为长度为 11 的环、两条不同的无向重边构成长为 22 的环。普通无向边来回走两次,不算环。

任务 方法 结果
无向图判环或找一条环边 并查集 一条使合并失败的原图边
无向图恢复任意一个环 DFS 环的点序、边序
基环树找出唯一的环 剥叶法 全部环上点,再沿环恢复顺序
有向图恢复任意一个环 三色 DFS 按方向排列的点序、边序

一般图可能有很多环,本篇的恢复模板找到一个就停止。基环树恰好只有一个环,因此找到的就是它的全部环上点和边。结构与后续算法见 基环树。

1 并查集找环边

依次读入无向边 (u,v)(u,v),用 并查集 维护此前的连通关系:

  • 两端不连通:合并两个集合,保留这条边。
  • 两端已经连通:保留的边中已经存在 uu 到 vv 的路径,再加上当前边就形成环。

成功合并的边始终构成森林,因此它们之间的路径唯一。合并失败的这条原图边,一定在某个环上。

设 unite(u, v) 在 u,vu,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

前三条边已形成路径 3→2→1→43\to2\to1\to4。第 44 条边 (3,4)(3,4) 两端已经连通,所以它是一条环边。最后一条边只接上一片叶子。

1.1 基环树断边

基环树是连通且恰好含一个环的无向图,等价于一棵树增加一条边,因而有 nn 个点、nn 条边。

处理完基环树的全部边,恰有一次合并失败:保留的 n−1n-1 条边已经构成生成树,失败的那条边就是可以断开的环边。删去它后,原图变成树。

这适合只需要断开一条环边、再运行树上算法的题目。它不一定是输入的最后一条边;改变输入顺序,也可能选中环上的另一条边。在一般多环图中,删除一条这样的边后还可能有环。

模板输入格式如上,边编号为输入行的顺序,从 11 开始。有环时输出第一条失败边的 编号 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;
}

采用路径压缩与按大小合并,时间复杂度为 O(n+mα(n))O(n+m\alpha(n)),空间复杂度为 O(n)O(n)。

1.2 从一条边恢复环

如果还需要整个环,可以在成功合并时,额外将这条原图边存入邻接表。找到失败边 (u,v)(u,v) 后,在这片森林中用 BFS 搜索 uu 到 vv 的唯一路径,再补上失败边即可。

完整代码
#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 森林。

检查当前点 uu 的邻边时,跳过进入 uu 的那一条边。若遇到一个已访问的祖先 vv,则:

一个环=树上从 v 到 u 的路径+边 (u,v). \text{一个环}=\text{树上从 }v\text{ 到 }u\text{ 的路径}+\text{边 }(u,v).

DFS 栈为一二三四,四号点通过回边到达祖先二;环只包含二三四,不包含栈中的一,也不包含挂在三上的五

图中 DFS 路径为 1→2→3→41\to2\to3\to4,从 44 遇到祖先 22,恢复出的环是 2→3→4→22\to3\to4\to2。当前搜索栈里不一定全是环上点,祖先 22 之前的前缀不属于这个环。

2.1 时间戳与来边

令 dfn[u] 为首次访问时间。无向图 DFS 的非树边连接祖先与后代,因此只在 dfn[v] < dfn[u] 时,从后代向祖先恢复环;另一侧会看到较大的时间戳,不必再处理。自环单独用 v == u 识别。

同一条无向边在两端邻接表中共用一个编号。跳过来边应写成:

if (e.id == parent_edge[u]) continue;

不能跳过所有指向父亲顶点的边。如果父子之间有两条不同边,进入当前点的那条要跳过,另一条却恰好能构成长为 22 的环。

2.2 恢复点序与边序

沿 parent 从 uu 回到 vv,得到逆序点列,反转后为 v,…,uv,\ldots,u。相邻父子间的边,读取孩子的 parent_edge;最后补上回边 (u,v)(u,v)。草稿中回溯路径上的树边也必须一并记录,不能只标记回边。

三份恢复模板统一输出:第一行环长 kk,第二行 kk 个点,第三行 kk 条边的编号。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] 记录返回 uu 后继续检查哪条邻边。首次发现孩子时入栈,处理完全部邻边后才出栈,保持真正的深度优先顺序。遍历所有未访问点,因此非连通图也能处理。

每条边至多检查两次,找到环后只回溯一次,时间复杂度为 O(n+m)O(n+m),空间复杂度为 O(n+m)O(n+m)。显式栈避免长链导致递归栈过深。

3 基环树剥叶

如果已知图是基环树,可以不断删除度数为 11 的叶子。

环上每个点都有两条环边,不会被删成叶子;环外是一棵棵挂树,最外层叶子删除后,内部节点会逐渐成为新叶子。最终恰好留下唯一的环。前面的五点图只需删除点 55,便剩下 1,2,3,41,2,3,4。

用队列维护待删除点。删掉一个点时,将尚未删除邻点的度数减一,度数降到 11 就入队。代码也将初始孤立点入队,以便统一删除度数不超过 11 的点。

剥叶只能确定剩余的点集,不能得到环序。在基环树中,剩下每个点的度数恰好为 22,从任一点出发,每次选择不是来边的另一条环边,就能绕行一圈。仍应按边编号跳过来边,以支持重边。

完整代码
#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;
}

输入为连通基环树,m=nm=n。输出格式与无向 DFS 相同,二者的起点、方向可能不同。自环对度数贡献 22;沿环走时走过它就回到起点,因此也能输出长度为 11 的环。时间和空间复杂度均为 O(n+m)O(n+m)。

3.1 一般图的限制

一般无向图反复删除度数不超过 11 的点,得到的是 2-core,即剩余点的度数都至少为 22。这些点不一定都在某个简单环上。

两个三角形通过三七四这条路径连接;所有顶点度数至少为二,但七号点与两条连接边不在任何简单环上

图中点 77 的度数为 22,剥叶不会删掉它,但它只是两个环之间连接路径上的点。连接路径上的两条边都是桥,不属于任何环。因此,不能在一般图中把“剥叶剩余”直接当作“全部环上点”。

若已知每个连通块至多一个环,剥叶后确实只剩各个环,但还需要逐个分组、分别绕行。上面的单环模板只输出其中一个,不能直接当作所有环的枚举器。

4 有向图找环

有向图的边有方向,不能直接使用普通并查集判定有向环。例如 1→2,1→3,3→21\to2,1\to3,3\to2 没有有向环,但忽略方向后形成三角形。

DFS 时也不能将“到达已访问点”等同于“发现环”。同一个例子中,先搜索完点 22,再走 1→3→21\to3\to2,会遇到已访问的 22,却没有返回当前路径的通路。

需要区分三种状态:

color 含义
00 尚未访问
11 已进入,仍在当前 DFS 路径上
22 邻边全部检查完毕,已退出当前路径

从 uu 检查有向边 u→vu\to v 时:未访问则继续搜索;若 color[v] == 1,树上已有有向路径 v→⋯→uv\to\cdots\to u,加上当前边就闭合成环;若为 22,继续检查其他边。

左图点 2 已退栈(color=2),边 3 到 2 为横叉边不成环;右图点 2 仍在当前路径上(color=1),回边 3 到 2 闭合为有向环

恢复方式仍是沿父亲回溯,再反转点列,边序必须与方向一致。有向图不跳过指向父亲的边:父亲到孩子的树边与孩子返回父亲的边,已经构成一个有向环。

完整代码
#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;
}

模板按有向边读入,每条边只存一次,使用显式栈并遍历所有连通部分。输出约定与前面的恢复模板一致,但每条边必须沿输入方向连接相邻点。时间和空间复杂度均为 O(n+m)O(n+m)。

如果只需判断有向图是否有环,也可以用 拓扑排序:无法输出全部顶点就说明存在环。不过一般有向图中,Kahn 算法留下的顶点可能包含环的后继,不能直接当作环上点。

本文模板按 n≤200000n\le200000 预留点数组;无向 DFS 的边标记数组按 m≤400000m\le400000 预留,实际使用时根据题目上限调整。

5 相关题解

暂无相关题解