docs/graph/bcc.md
在阅读下列内容之前，请务必了解 图论相关概念 部分．
相关阅读：割点和桥
割点和桥更严谨的定义参见 图论相关概念．
在一张连通的无向图中，对于两个点 $u$ 和 $v$，如果无论删去哪条边（只能删去一条）都不能使它们不连通，我们就说 $u$ 和 $v$ 边双连通．
在一张连通的无向图中，对于两个点 $u$ 和 $v$，如果无论删去哪个点（只能删去一个，且不能删 $u$ 和 $v$ 自己）都不能使它们不连通，我们就说 $u$ 和 $v$ 点双连通．
边双连通具有传递性，即，若 $x,y$ 边双连通，$y,z$ 边双连通，则 $x,z$ 边双连通．
点双连通 不 具有传递性，反例如下图，$A,B$ 点双连通，$B,C$ 点双连通，而 $A,C$ 不 点双连通．
对于一个无向图中的 极大 边双连通的子图，我们称这个子图为一个 边双连通分量．
对于一个无向图中的 极大 点双连通的子图，我们称这个子图为一个 点双连通分量．
对于一张连通的无向图，我们可以从任意一点开始 DFS，得到原图的一棵 DFS 生成树（以开始 DFS 的那个点为根），这棵生成树上的边称作 树边，不在生成树上的边称作 非树边．
由于 DFS 的性质，我们可以保证所有非树边连接的两个点在生成树上都满足其中一个是另一个的祖先．
DFS 的代码如下：
???+ note "实现"
=== "C++"
cpp void DFS(int p) { visited[p] = true; for (int to : edge[p]) if (!visited[to]) DFS(to); }
=== "Python"
```python
def DFS(p):
visited[p] = True
for to in edge[p]:
if visited[to] == False:
DFS(to)
```
???+ note "例题：洛谷 P8436【模版】边双连通分量" 对于一个 $n$ 个节点 $m$ 条无向边的图，请输出其边双连通分量的个数，并且输出每个边双连通分量．
用 Tarjan 求双连通分量过程与求强连通分量类似，可以先阅读 强连通分量 的 Tarjan 算法．
我们考虑先求出所有的桥，再 DFS 求出边双连通分量．
求桥可参见 割点和桥 的桥部分．
时间复杂度 $O(n+m)$．
??? note "示例代码"
cpp --8<-- "docs/graph/code/bcc/bcc_1.cpp"
我们先总结出一个重要的性质，在无向图中，DFS 生成树上的边不是树边就只有非树边．
我们联系一下求强连通分量的方法，在无向图中只要一个分量没有桥，那么在 DFS 生成树上，它的所有点都在同一个强连通分量中．
反过来，在 DFS 生成树上的一个强连通分量，在原无向图中是边双连通分量．
可以发现，求边双连通分量的过程实际上就是求强连通分量的过程．
时间复杂度 $O(n+m)$．
??? note "示例代码"
cpp --8<-- "docs/graph/code/bcc/bcc_2.cpp"
和 Tarjan 算法 1 类似，我们先求出所有的桥，再差分求出边双连通分量．
首先，对原图进行 DFS．
如上图所示，黑色与绿色边为树边，红色边为非树边．每一条非树边的两个端点都唯一对应了树上的一条由树边构成的简单路径，我们说这条非树边 覆盖 了这条简单路径上所有的边．
在图中，绿色的树边 至少 被一条非树边覆盖，黑色的树边不被 任何 非树边覆盖．
显然，非树边 和 绿色的树边 一定不是桥，黑色的树边 一定是桥．
首先考虑一个暴力的做法，对于每一条非树边，都逐个地将它覆盖的每一条树边置成绿色，时间复杂度为 $O(nm)$．
考虑用差分优化．对于每一条非树边，在其树上深度较小的端点处打上 -1 标记，在其树上深度较大的端点处打上 +1 标记，然后 $O(n)$ 求出每个点的子树内部的标记和．
对于一个点 $u$，其子树内部的标记之和等于覆盖了 $u$ 和 $fa_u$ 之间的树边的非树边数量．若这个值等于 $0$，则 $u$ 和 $fa_u$ 之间的树边是 桥．
再用 DFS 求出边双连通分量．
时间复杂度 $O(n+m)$．
??? note "示例代码"
cpp --8<-- "docs/graph/code/bcc/bcc_4.cpp"
???+ note "#2788.「CEOI2015 Day1」管道" 给出一个 $N$ 点 $M$ 边的无向图，不保证连通．将每个联通块视为子图，请求出每一个子图中的桥．你只有 16 MB 的内存空间．
??? note "题解" 此题最大的特征在于，你存不下所有的边．
考虑优化存边，若一条非树边被另一条非树边完全覆盖，则这条边无用．
用并查集维护即可．
???+ note "例题：洛谷 P8435【模板】点双连通分量" 对于一个 $n$ 个节点 $m$ 条无向边的图，请输出其点双连通分量的个数，并且输出每个点双连通分量．
需要先学习割点，可以先参见 割点和桥 的割点部分．
先给出两个性质：
我们根据第二个性质，分类讨论：
??? note "示例代码"
cpp --8<-- "docs/graph/code/bcc/bcc_3.cpp"
如上图所示，黑色边为树边，红色边为非树边，每一条非树边的两个端点都唯一对应了树上由树边构成的的一条简单路径．
考虑一张新图，新图中的每一个点对应原图中的每一条树边（在图中用蓝色点表示）．对于原图中的每一条非树边，将这条非树边对应的树上简单路径中的所有边在新图中对应的蓝点连成一个连通块（在图中用蓝色的边体现出来）．
这样，一个点若 不是 割点，当且仅当与其相连的所有边在新图中对应的蓝点都 属于 同一个连通块．
两个点 是 点双连通，当且仅当它们在原图的树上路径中的所有边在新图中对应的蓝点都 属于 同一个连通块，即图中的每个蓝点构成的连通块都是一个点双连通分量．
蓝点间的连通关系可以用与求边双连通时用到的差分类似的方法维护，时间复杂度 $O(n+m)$．