我的算法书 - 无向图找环

一句话算法

基环树找环可以不用复杂 DFS：不断删掉叶子，最后剩下的点就是环。

问题模型

这里讨论最常见的无向基环树找环：

图是无向图。
每个连通块最多一个环。
目标是找出所有在环上的点。

如果是普通无向图，可能有很多环，问题会变成环检测、最小环、点双/边双等不同模型，不能只靠一个基环树模板解决。

核心直觉

环上的点至少有两条环边，所以它不会在删叶子的过程中先变成孤立树枝。环外挂着的是树，树一定有叶子。把叶子一层层剥掉，树枝会被全部删完，环会留下。

算法步骤

统计所有点的度数。
把度数不超过 1 的点入队。
每次删除一个队首点，并让它的邻点度数减一。
如果邻点度数变成 1，继续入队。
队列清空后，没被删除的点就是环上点。

算法证明

关键不变量： 每次被删除的点都不在环上。

度数小于 2 的点不可能在环上。
删除一个非环点，只会让环外树枝继续变短，不会删除真正的环边。
新出现的度数为 1 的点仍然是环外树枝的叶子。
所有环外树枝都会被逐层删除，剩下的只能是环上点。

复杂度分析

每个点最多入队一次，每条边最多被检查两次。

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

代码实现

cpp

        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

        #include <bits/stdc++.h>
using namespace std;

struct PseudotreeCycle {
    int n;
    vector<vector<int>> graph;
    vector<int> degree;
    vector<bool> in_cycle;

    explicit PseudotreeCycle(int n)
        : n(n), graph(n + 1), degree(n + 1, 0), in_cycle(n + 1, true) {}

    void add_edge(int u, int v) {
        graph[u].push_back(v);
        graph[v].push_back(u);
        ++degree[u];
        ++degree[v];
    }

    vector<int> find_cycle_nodes() {
        queue<int> q;
        for (int i = 1; i <= n; ++i) {
            if (degree[i] <= 1) q.push(i);
        }

        while (!q.empty()) {
            int u = q.front();
            q.pop();
            if (!in_cycle[u]) continue;

            in_cycle[u] = false;
            for (int v : graph[u]) {
                if (!in_cycle[v]) continue;
                --degree[v];
                if (degree[v] == 1) q.push(v);
            }
        }

        vector<int> cycle_nodes;
        for (int i = 1; i <= n; ++i) {
            if (in_cycle[i]) cycle_nodes.push_back(i);
        }
        return cycle_nodes;
    }
};

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

    int n, m;
    cin >> n >> m;

    PseudotreeCycle solver(n);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        solver.add_edge(u, v);
    }

    vector<int> cycle_nodes = solver.find_cycle_nodes();
    for (int u : cycle_nodes) cout << u << ' ';
    cout << '\n';
    return 0;
}

测试用例

输入：

输出：

1 2 3

应用分类详解

一、基环树找环

典型模式： 点数和边数相等，图连通，只有一个环。 识别信号： 题面明确说“基环树”“环套树”，或者每个连通块边数等于点数。 核心建模： 删叶子得到环点，再处理挂在环上的树。

应用场景	经典题目	核心思路
基环树 DP	luogu-P2607	找环后环外树 DP，环上分类讨论
基环树直径	luogu-P4381	找环后合并树深和环距离

二、普通图找环

典型模式： 图中可能有很多环，只需要判断是否存在环。 识别信号： 题目不保证基环树，边数可能远大于点数。 核心建模： 无向图可以用 DFS 父边判断，或者用并查集逐边加边检测成环。

应用场景	经典题目	核心思路
并查集判环	luogu-P3367	加边时两个端点已连通则形成环

经典例题

luogu-P2607 基环树 DP 入门，先找环再处理环外树。
luogu-P4381 基环树直径，找环是后续环上计算的前置步骤。
luogu-P5022 基环树断边枚举，必须先知道环上的候选边。