Acasă Explorează Ajutor
Autentificare
wfirstzhang
/
lessons
oglindă de https://gitee.com/wfz7789/noip_lessons.git
1
0
Bifurcare 0
Fisiere Probleme 0 Wiki
Arbore: 52bd18832a
Ramuri Etichete
lessons
/
课程
/
02-强连通与双连通
/
02-桥边双连通与桥树.md

02-桥边双连通与桥树.md 9.2 KB
Istoric Crud

桥、边双连通分量与桥树

本节目标

学完后，你应能在线性时间找出无向图中的桥（bridge），按删桥后的连通块得到边双连通分量（edge-biconnected component, e-BCC），并把原图压成桥树解决直径、补边和最优定向问题。

前置知识与课前自测

前置：无向 DFS、树的直径、上一节的 dfn/low 思想。

  1. 一条边在环上时可能是桥吗？
  2. DFS 子树 $v$ 通过返祖边恰好回到父亲 $u$，边 $(u,v)$ 是桥吗？
  3. 判断父边时只写 if (v == parent) continue，遇到重边会怎样？
自测答案 1. 不可能；删掉它还能沿环的另一侧连通。 2. 不是。桥的严格条件是 `low[v] > dfn[u]`，等号表示存在另一条回到 $u$ 的路。 3. 两条平行边都会被当成父边跳过，可能把本来不该是桥的边误判为桥；应按边编号跳过恰好一条父边。

问题动机与步步推导

逐条删边再做连通性检查是 $O(E(V+E))$。DFS 树已经把“删一条树边会隔开哪一块”固定下来：对树边 $u-v$，只需问 $v$ 的整棵子树能否通过别的边回到 $u$ 或更早祖先。

定义 low[v] 为 $v$ 子树通过树边和任意多条非父边能返回祖先或子树内节点的最小 dfn。完成子树后：

$$ (u,v)\text{ 是桥}\iff low[v]>dfn[u]. $$

删除全部桥后，每个剩余连通块内部任意两点之间都有两条边不相交路径；把每块缩成点、把桥保留，连通原图得到一棵树，非连通原图得到森林。若缩点后仍有环，环上的“桥”就能绕行，矛盾。

核心知识与实现指南

递归模板很短，但本节例题达到 $4\times10^5$ 个点，课程参考实现采用显式栈模拟 DFS：

  • parent_edge[v] 记录把 $v$ 带入 DFS 树的边编号；
  • cursor[u] 记录邻接表扫描位置；
  • 弹出 $v$ 时才把 low[v] 合并给父亲并判桥；
  • 已访问邻点用 dfn[to] 更新，指向后代时这个值更大，不会错误降低 low。

每点、每条邻接记录只进出常数次，时间 $O(V+E)$，空间 $O(V+E)$。

精选例题 1：We Need More Bosses

来源信息与题意

给定连通简单无向图，$2\le n\le3\times10^5$，$n-1\le m\le3\times10^5$。任选起终点 $s,t$，所有从 $s$ 到 $t$ 都必须经过的边可放置 Boss。求最多能放多少个。

Hint 1“所有路线都必须经过”的边正是分隔 $s,t$ 的桥。
Hint 2把边双连通分量缩点后，$s,t$ 之间的必经桥数就是桥树距离。
Hint 3任选 $s,t$ 最大化树上距离，就是求桥树直径。

Observations、Editorial 与证明

非桥位于某个环上，可以绕开；桥删去后两侧断开，若 $s,t$ 分居两侧就必经。缩点后每条树边对应一座桥，因此指定 $s,t$ 的 Boss 数等于其分量在桥树中的距离。树上最大两点距离是直径，用两次 BFS 求得。

桥判定、缩点、建树、两次 BFS 都是线性，总复杂度 $O(n+m)$。

核心伪代码与参考实现附件

bridges = find_bridges_with_edge_ids(graph)
component = flood_fill_while_ignoring(bridges)
bridge_tree = contract_components_and_keep_bridges()
a = farthest_vertex(bridge_tree, arbitrary_root)
b, distance = farthest_vertex(bridge_tree, a)
output distance

完整 GNU C++17 参考实现见附件：CodeForces-1000E.cpp

复盘与变式

若边有权且目标是必经桥权值和最大，桥树直径改为带权直径；非桥权值仍不计入，因为它们都可绕开。

精选例题 2：Redundant Paths

来源信息与题意

  • VJudge：POJ-3177 Redundant Paths
  • 原来源：USACO 2006 January Gold
  • 大致难度：提高；考点：桥树叶子配对、重边

连通无向图有 $1\le F\le5000$ 个点、$F-1\le R\le10^4$ 条边，允许重边。至少增加多少条边，才能使任意两点之间存在两条边不相交路线？允许新增平行边。

Hint 1目标等价于整张图不再有桥。
Hint 2缩成桥树后，一次新增边会让树上两端之间整条路径的桥进入环。
Hint 3度数为 1 的叶分量每个都必须获得一条“向外的新连接”；一条新边最多照顾两个叶子。

Observations、Editorial 与证明

桥树有 $L$ 个叶子。每个叶子只靠一座桥连接外界，要消除这座桥，至少有一条新增边跨出该叶子，因此至少需要 $\lceil L/2\rceil$ 条。把叶子两两配对并连接各自分量内任一点，新增边与树上路径组成环，覆盖路径上的桥；奇数个叶子时最后一叶与已使用叶适当连接，仍只需 $(L+1)/2$ 条。下界可达。

若缩点后只有一个点，叶数为 0，答案为 0。复杂度 $O(F+R)$。

核心伪代码与参考实现附件

bridges = find_bridges_with_edge_ids(graph)
component = flood_fill_while_ignoring(bridges)
degree = degrees in the contracted bridge tree
leaves = count(degree == 1)
output ceil(leaves / 2)

完整 GNU C++17 参考实现见附件：POJ-3177.cpp

复盘与变式

允许重边使“按父顶点跳边”的写法必错。若原图不连通，还必须先连接不同树，答案不能对每棵桥树简单独立取整后相加。

精选例题 3：Tourist Reform

来源信息与题意

给定连通简单无向图，$2\le n,m\le4\times10^5$。给每条边定向，令 $r_i$ 为从 $i$ 可达的城市数，最大化 $\min r_i$，并按输入顺序输出定向。

Hint 1缩成桥树后，任意定向的树必有一个出度为 0 的汇分量。
Hint 2汇分量中的点无法经过桥到外部，所以答案不超过某个边双分量大小，进而不超过最大分量大小。
Hint 3选最大边双分量为根，把所有桥朝根定向；每个分量内部做强连通定向。
Hint 4无桥连通图中，DFS 树边向下、返祖边向上可得到强连通定向。

Observations、Editorial 与证明

任何桥树定向都有汇点，汇边双分量内的点只能到达该分量内部，因此最小可达数不超过最大边双分量大小 $S$。

选大小为 $S$ 的分量作根，所有桥由子分量指向父分量。每个无桥分量内部按 DFS 树边向下、返祖边向上定向；无桥条件保证每条树边的子树都有返祖通路回到祖先，从而分量强连通。任意一个非根分量的点能先在分量内到达朝根桥的起点，逐层进入根，到达根内全部 $S$ 个点；根内任意点至少能到达根内自身与其他同分量点共 $S$ 个点（再经指出的桥向其子分量扩展可达更多点，但不影响下界）。因此 $\min r_i \ge S$，与上界相等，达到最优。

核心伪代码与参考实现附件

find bridges and edge-biconnected components
root = component with maximum number of original vertices
inside each component: orient DFS-tree edges down and back edges up
build the bridge tree rooted at root
orient every bridge from child component toward parent component
output size(root) and all orientations in input order

完整 GNU C++17 参考实现见附件：CodeForces-732F.cpp

复盘与变式

本题的关键是“任意树定向必有汇点”给出上界，而不是先猜构造。若目标改成最大化平均可达数，把桥全部朝一个根定向未必最优，上界结构也会改变。

扩展与联系

  • 无桥连通无向图存在强连通定向，这是 Robbins 定理；DFS 定向同时给出构造。
  • 桥树上的路径计数、直径、中心与差分都可复用普通树算法。
  • 点双连通关注删点而非删边，缩点结构不再是一棵普通“点不重叠”的树，见下一节圆方树思想。

总结与自检

  1. 为什么判桥使用严格大于？
  2. 为什么重边要求按边编号跳父边？
  3. We Need More Bosses 为什么是桥树直径？
  4. Redundant Paths 的叶子下界如何由一条新增边达到两个端点？
  5. Tourist Reform 的上界和达到上界的构造分别是什么？

课后训练建议

先对拍桥判定：随机删一条边，比较连通块数量是否增加。再做桥树直径与叶子计数。Tourist Reform 可先只口述上界和定向方向，再实现；调试时分别验证每条原边恰输出一次、非桥分量强连通、所有桥指向所选根。