KACTL 算法笔记

053-图论-双连通分量

6 min read

  1. 核心概述 在无向图上用 Tarjan 栈与时间戳一次 DFS 提取所有边双连通分量（BCC），识别桥与按分量消费边集合，时间 O(V+E)。

  2. 原文引述

Description: Finds all biconnected components in an undirected graph, and runs a callback for the edges in each. In a biconnected component there are at least two distinct paths between any two nodes. Note that a node can be in several components. An edge which is not in a component is a bridge, i.e., not part of any cycle. Time: O(E + V)

  1. 展开阐述

  • 定义与背景

    • 边双连通分量（edge-biconnected component）：无向图中任意两点间至少存在两条边不相交的路径；去掉任一条边仍连通。与之互补的“桥”是任何不在环上的边（删除会使连通块数增加）。
    • 本实现面向“边分量”：每个 BCC 输出为一组边；“点双连通分量”与“割点”可在相同框架下提取，但边界判据略有不同。

  • 数据结构（据实现）

    • num[u]：DFS 进入时间/时间戳；Time 作为全局自增计数器。
    • st：边栈，保存当前 DFS 递归分支上的“候选 BCC 边”。
    • ed：邻接表，元素为 (v, eid)；父边用边 ID 识别避免与返祖边混淆。

  • 核心流程/要点（Tarjan BCC）

    1. 递归框架 dfs(u, peid, f)
      • 设定 num[u] = ++Time，初始化 top = num[u]。
      • 遍历每条邻边 (v, eid)：
        • 若 v 已访问且 eid != peid（后向/横向到祖先）：top = min(top, num[v])；若 num[v] < num[u]，将 eid 压栈（属于当前搜索支）。
        • 若 v 未访问：递归 up = dfs(v, eid, f)，然后：
          • top = min(top, up)
          • 若 up == num[u]：说明以 u 为“BCC 根”的分量闭合。把栈顶弹到当前边 eid 为止，构成一个完整边集，调用回调 f(edges)。
          • 若 up < num[u]：将 eid 压栈（该边位于某个上层 BCC 中）。
          • 否则（up > num[u]）：eid 为桥（不属于任何 BCC），可即时记录或留空。
      • 返回 top（lowlink）。
    2. “桥/分量”边界直觉
      • up(v) = 到 v 子树能追溯到的最早祖先时间戳。
      • 若 up(v) ≥ num[u] 则 (u,v) 切断“回到 u 之前祖先”的途径，针对“点双/割点”；而在“边双/桥”场景，up(v) > num[u] 判桥，up(v) == num[u] 触发一次边分量弹栈。
    3. 回调消费
      • 模板接口 bicomps(F f) 将每个 BCC 的边集合传入 f，便于在线构建“分量树”、统计答案或标注分量 ID。
    4. 正确性与不变式
      • 栈中始终保持“当前递归路径上、尚未归属分量”的边；一旦检测到根条件，就把属于该分量的边一次性弹出并提交。
      • num/low 的单调与“祖先可达性”不变式保证“恰好一次”输出每条边，且分量不交叠。

  • 复杂度与边界条件

    • 单次 DFS，时间 O(V+E)，空间 O(V+E)（递归栈 + 边栈）。
    • 多连通块：对每个未访问的起点调用 dfs。
    • 自环/重边：自环单独形成长度 1 的环，按实现可能成为独立 BCC；重边可形成 2 边环，不会被误判为桥。
    • 回调成本：整体复杂度包含对每个 BCC 调用 f 的线性成本，应避免在回调内做高于线性的额外处理。

  • 变体/扩展

    • 点双连通分量与割点：以“up(child) ≥ num[u]”识别割点；分量按“顶点集合”组织，栈可存边或点入栈边界略有差异。
    • 桥与“桥树/圆方树”：将每个边 BCC 缩点得到“桥树”，或构建圆方树以同时承载点与 BCC（用于路径/覆盖类题）。
    • 联合并查集：离线场景可用并查集合并非桥边；但在线输出分量仍以 Tarjan 更直接。

  • 与相邻技术对比与取舍

    • 与 077-图论-强连通分量：SCC 针对有向图；BCC 针对无向图，目标和判据不同。
    • 与“块点树/圆方树”：BCC 是基础分解；后者是其结构化表达，适用于进一步的树上 DP 或路径统计。
    • 与“桥检测（仅识别是否为桥）”：若仅需要桥，可省去栈与回调，判 up(v) > num[u] 即可。
  1. 关联节点

Graph View

Backlinks