基环树入门

基环树入门：找环方法与基环树上的经典问题。

  • 基环树
  • 找环
  • 图论

一句话算法

基环树就是一棵树多了一条边；先找出唯一的环，再把环上每个点挂着的部分当成树处理。

问题模型

无向基环树是一个连通图，满足：

  • 有 nn 个点。
  • 有 nn 条边。
  • 图中恰好有一个简单环。

如果图不保证连通，但每个连通块都是基环树，那么它叫基环树森林。

核心直觉

一棵树有 n−1n-1 条边。往树上再加一条边，就会把原来两点之间的路径和这条新边围成一个环。环上的点可能挂着若干棵树，所以基环树常被理解成“环 + 若干棵挂在环上的树”。

无向基环树：

无向基环树

有向基环树中，常见的是每个点出度为 1 的函数图。所有点沿出边走，最终都会进入某个环。

通用处理框架

处理基环树问题，通常按三步走：

  1. 找环： 标记哪些点在环上。
  2. 处理树： 从每个环点出发，把挂在它下面的树形部分单独 DP 或统计。
  3. 处理环： 把每个环点的树形结果压缩成环上的权值，再做环形 DP、断环成链或单调队列优化。

算法步骤

无向基环树最稳的找环方法是不断删除度为 1 的点。

  1. 统计每个点的度数。
  2. 把所有度数不超过 1 的点放入队列。
  3. 每次弹出一个点 u，把它标记为“不在环上”。
  4. 对 u 的邻点 v，如果 v 仍未被删除，则令 degree[v]--。
  5. 如果 degree[v] 变成 1，说明它也成了新的叶子，入队。
  6. 队列清空后，所有没被删除的点就是环上点。

算法证明

关键不变量： 被删除的点一定不在任何环上。

  1. 度数为 0 或 1 的点不可能在环上，因为环上每个点至少有两条环边。
  2. 删除叶子点只会剥掉挂在环外的树枝，不会破坏真正的环。
  3. 删除一层叶子后，新出现的叶子仍然只能属于环外树枝。
  4. 不断重复后，所有环外树枝都会被剥掉，剩下的只能是环。

复杂度分析

设点数为 nn，边数为 mm。

  • 建图需要 O(n+m)O(n+m) 时间和 O(n+m)O(n+m) 空间。
  • 每个点最多入队一次，每条边在相邻点删叶时最多被检查常数次。
  • 因此找环总时间复杂度为 O(n+m)O(n+m)，空间复杂度为 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;
}

测试用例

输入：

6 6
1 2
2 3
3 1
3 4
4 5
4 6

输出：

1 2 3

点 1,2,3 构成唯一的环，4,5,6 都是挂在环外的树形部分。

应用分类详解

基环树的本质是“树上问题 + 一个环”。

一、找环后做树形 DP

典型模式： 图是基环树或每点出度为 1，要求最大权独立集、选点、覆盖等。 识别信号： 点数和边数相等，或者题面暗示每个点只连向一个后继。 核心建模： 先找环，环外按树形 DP，环上再处理首尾相邻限制。

应用场景 经典题目 核心思路
基环树 DP luogu-P2607 环上每个点挂一棵树，最后在环上做分类讨论
函数图 DP CF711D 每个点出度为 1，连通块是有向基环树

二、基环树直径与距离

典型模式： 求基环树中最长路径或两点距离。 识别信号： 图中存在唯一环，环外是树。 核心建模： 环外先求每个环点向外的最大深度，再在环上做环形最大值计算。

应用场景 经典题目 核心思路
基环树直径 luogu-P4381 子树深度 + 环上两点距离组合
快餐店模型 NOI2013 快餐店 环上断点、树深和环距离共同决定答案

三、字典序与断边枚举

典型模式： 基环树只比树多一条边，要得到某种树结构结果。 识别信号： 删除环上一条边后就变成树。 核心建模： 找到环边，枚举或贪心选择删哪条边，再套树算法。

应用场景 经典题目 核心思路
基环树断边 luogu-P5022 找环后枚举删除环边，比较 DFS 序

经典例题

  1. luogu-P2607 基环树 DP 入门。重点是环上相邻点不能同时选的处理。

  2. luogu-P4381 基环树直径经典题。需要把树上深度和环上距离结合起来。

  3. luogu-P5022 基环树断边枚举。适合理解“基环树删一条环边就是树”。

参考