基环树入门

定义

基环树（Pseudo-tree），有时也被称为环套树，是图论中的一个概念。严格来说，它并不是一棵树，而是一个包含 n 个节点和 n 条边的连通图。

从结构上看，一棵 n 个节点的树有 n-1 条边，如果在树上任意两个节点之间添加一条边，就会形成一个且仅有一个环。因此，基环树可以被理解为一棵树加上一条额外的边所构成的图。

如果图不保证连通，那么一个含有 n 个节点和 n 条边的图可能是一个基环树森林（Pseudo-forest），即由若干个基环树组成。

无向基环树

在无向图中，基环树的结构就是一个简单的环，环上的每个节点都可能连接着一棵或多棵子树。

无向基环树

有向基环树

在有向图中，根据边的方向，基环树可以分为两种主要类型：

内向基环树 (In-tree)

每个节点都恰好有一条出边（出度为 1）。其形态表现为，所有节点最终都通过有向边汇聚到一个环上。环外的节点构成了若干棵树，树边全部指向环的方向。

内向基环树

外向基环树 (Out-tree)

每个节点都恰好有一条入边（入度为 1）。其形态与内向树相反，所有边都从环开始，向外发散。环外的节点也构成若干棵树，树边全部背离环的方向。

外向基环树

通用处理思路

处理基环树相关的问题，通常有一个经典的分析框架：

  1. 找到环：首先，通过算法定位图中唯一的环。
  2. 处理子树：将环上的每个节点视为根，其向外连接的部分就构成了一棵棵独立的子树。我们可以利用树形算法（如树形 DP）对这些子树进行预处理。
  3. 环上计算：将子树的处理结果整合到环上，再利用适用于序列或环的算法（如线性 DP、单调队列优化等）来解决整个问题。

如何找环

在基环树中找到环是解决问题的第一步。最常用的方法是深度优先搜索 (DFS)。

算法思路

  1. 从任意一个未访问过的节点开始进行深度优先搜索。
  2. 在搜索过程中，我们需要记录每个节点的父节点（即从哪个节点访问到当前节点的），同时用一个 visited 数组记录节点是否被访问过。
  3. 当从节点 u 访问邻接节点 v 时：
    • 如果 v 未被访问，则继续向 v 深入搜索，并记 parent[v] = u。
    • 如果 v 已被访问过，并且 v 不是 u 的父节点，那么就意味着我们找到了一个环。节点 v 是环的入口，而 (u, v) 是一条“返祖边”。
  4. 找到环后，我们可以从 u 开始，通过 parent 指针不断回溯，直到再次遇到 v。这条回溯路径上的所有节点，再加上 v，就构成了基环树中的环。

这个过程可以通过在 DFS 中维护一个递归栈来实现，当遇到一个已在当前递归栈中的节点时，就找到了环。

相关问题

基环树模型在算法竞赛中很常见，典型的例题包括：

  • 求基环树的直径
  • 基环树上的动态规划问题
  • 寻找图中距离某点最远的点

topsrt找环

topsort

思路 : 不停的删除度为1 的点,最会剩余的点就在环上.

dfs找环

思路:

容易想到

  1. 记录每个的点的dfs序dfn[u]
  2. 在树上dfs时,不可能遇到返组边,已经访问过的更大dfn值的点
  3. 在基环树上 返祖边,已经访问过的更大dfn值的点 各一次,且是同一条边

于是我们可以写出下面的代码

cpp
copy 
        
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

        // loop: 存储环路上的节点,loop_cnt: 环路上的节点数量
int loop[maxn],loop_cnt;
// dfn: 节点在DFS过程中的访问时间戳 (discovery time)
// dfn_idx: 时间戳计数器
int dfn[maxn],dfn_idx;
int fa[maxn]; // fa: 在DFS树中，节点的父节点

/**
 * @brief 通过DFS寻找图中的环.
 * 该函数适用于有向图，它寻找由前向边构成的环.
 * @param u 当前访问的节点
 * @param father u在DFS树中的父节点
 */
void get_ring(int u, int father)
{
    // 为当前节点u分配一个访问时间戳
    dfn[u] = ++dfn_idx;
    // 记录u的父节点
    fa[u] = father;

    for (int i = e.h[u]; i != -1; i = e[i].next)
    {
        int v = e[i].v; // 邻接点
        
        // 如果v已经被访问过
        if (dfn[v])
        {
            // 如果v是u的祖先节点(返祖边),则跳过
            if (dfn[v] < dfn[u]) continue; // 返祖边略过

            // 找到一个环: u -> v, 并且v是u的后代(前向边)
            // v的时间戳比u大，说明v在u的DFS子树中
            
            // 从v开始，通过父节点指针回溯到u，记录路径上的所有节点
            for( ; v != u ; v = fa[v]) loop[++loop_cnt] = v;
            loop[++loop_cnt] = u;
        }
        else get_ring(v, u);
    }
}
点击

好的，我们来详细拆解和理解这行代码 if (dfn[v] < dfn[u]) continue; 的作用。

这行代码是利用深度优先搜索（DFS）在基环树中找环的关键部分。为了理解它，我们需要先明白dfn数组和整个DFS过程的含义。

1. 基础概念

  • 基环树 (Unicyclic Graph): 一个有 N 个点、N 条边的连通图。它的结构可以看作是一棵树，上面额外多了一条边，从而形成了一个唯一的环。
  • DFS (深度优先搜索): 代码中的 get_loop 函数本质上是一个DFS。
  • dfn[u] (Discovery Time / Timestamp): dfn 是 “depth-first number” 的缩写。dfn[u] = ++idx; 这行代码给每个节点 u 在DFS中被访问到的顺序打上了一个时间戳。先被访问到的节点 dfn 值小，后被访问到的 dfn 值大。
  • fa[u] (Parent): 记录在DFS树中，节点 u 是由哪个节点访问过来的。fa[u] 是 u 的父节点。
  • 找环的原理: 在DFS过程中，如果从当前节点 u 访问到一个邻居节点 v，而 v 之前已经被访问过了（即 dfn[v] 不为0），并且 v 不是 u 的父节点（v != fa[u]），那么我们就找到了一条“返祖边”，说明发现了一个环。

2. 核心问题：为什么要有 if (dfn[v] < dfn[u]) continue;？

在基环树的DFS中，当找到环时，实际上会有两次机会检测到这个环。

让我们用一个例子来说明。假设环是 A - B - C - D - A。我们的DFS从环外的一个点开始，通过 E 进入了环，访问顺序是 E -> A -> B -> C -> D。

此时的dfn和fa状态如下：

  • dfn[E] < dfn[A] < dfn[B] < dfn[C] < dfn[D]
  • fa[A] = E, fa[B] = A, fa[C] = B, fa[D] = C

现在，DFS到达了节点 D。

第一次相遇 (深节点 D 遇到浅节点 A)

  1. 当前节点: u = D。
  2. 遍历邻居: D 的邻居有 C 和 A。
    • 当邻居是 C 时，C == fa[D]，所以 continue，这是为了防止DFS走回头路。
    • 当邻居是 A 时，v = A。
  3. 判断:
    • v != fa[u] ( A != C ) -> True
    • dfn[v] ( dfn[A] ) > 0 -> True，说明 A 被访问过，我们找到了环！
  4. 进入关键代码: if (dfn[v] < dfn[u])
    • dfn[A] < dfn[D] 是成立的，因为 A 比 D 先被访问。
    • 所以 continue 被执行。
    • 这次相遇被忽略了！

为什么忽略？因为在这个时刻，A 是 D 在DFS树中的祖先。如果我们在这里处理环，逻辑会比较复杂。而这段代码的设计者选择了一种更简洁的处理方式。

第二次相遇 (浅节点 A 遇到深节点 D)

  1. DFS从 D 返回，然后从 C 返回，从 B 返回，最终回到 A。
  2. 当前节点: u = A。A 已经完成了对邻居 B 的所有深度搜索。
  3. 遍历邻居: A 的邻居有 E, B, D。
    • 当邻居是 E 时，E == fa[A]，continue。
    • 当邻居是 B 时，对 B 的DFS已经完成，B 是 A 的子节点。
    • 当邻居是 D 时，v = D。
  4. 判断:
    • v != fa[u] ( D != E ) -> True
    • dfn[v] ( dfn[D] ) > 0 -> True，D 被访问过，我们又找到了环！
  5. 进入关键代码: if (dfn[v] < dfn[u])
    • dfn[D] < dfn[A] 不成立，因为 dfn[D] > dfn[A]。
    • 所以 continue 不被执行。
  6. 执行找环逻辑:
    • loop[++cnt] = v; // D 被加入环
    • for (; v != u; v = fa[v]) // 从 D 开始，通过 fa 指针往回走
      • v=D, fa[D]=C。C 被加入环。
      • v=C, fa[C]=B。B 被加入环。
      • v=B, fa[B]=A。A 被加入环。
      • v 变成 A，循环条件 v != u ( A != A ) 为假，循环结束。

此时，环上的所有节点 (D, C, B, A) 都被正确地找到了。

总结

这行代码 if (dfn[v] < dfn[u]) continue; 是一个巧妙的过滤器。

它的核心思想是：只在环上dfn值最小的那个节点（也就是DFS最先进入环的那个节点）去处理和记录整个环。

  • dfn[v] < dfn[u] 的情况:
    • 这表示当前节点 u 找到了一个它的祖先 v，形成了一个环。
    • 我们选择忽略这次发现，让DFS继续回溯。
  • dfn[v] > dfn[u] 的情况:
    • 这表示当前节点 u (一个祖先) 找到了一个它的后代 v，而这个后代 v 之前已经被访问过了（说明 u 和 v 在同一个环上，并且 v 是通过另一条路径被访问的）。
    • u 就是这个环上dfn值最小的节点。
    • 这时，我们才开始执行找环的逻辑。因为从 v 到 u 的路径已经通过 fa 数组完整地记录下来了，可以方便地回溯并记录所有环上的节点。

通过这种方式，可以保证环只被发现和处理一次，并且是在一个最方便处理的位置（环的“顶部”），使得代码逻辑变得非常清晰和简单。

代码

dfs

思路

代码

基环树直径

基环树两点直接的距离

基环树DP

参考