浅谈连通性
NegetiveEdgeWeight
·
·
算法·理论
前言
连通性相关的算法其实主要目的就是缩点。求出强连通分量后可以把有向图缩成 DAG，而求出双连通分量后可以把无向图缩成树，利用 DAG 和树的拓扑结构解题。
阅读这篇文章的时候可以结合图片辅助理解。同时，文中大部分的证明都是可以在某种程度上感性理解的，可以选择性地阅读证明部分。
本文涉及到的内容有：DFS 生成树、强连通分量、双连通分量、割点割边、缩点、圆方树。
本文共有约 3.5k 字，预计阅读时间为 60 分钟。
连通性相关概念
约定本文中所有点、边的编号都是 1-indexed。
DFS 生成树
在求解连通分量的 Tarjan 算法中会频繁使用到 DFS 生成树。DFS 生成树是指在一个图上进行 DFS（深度优先搜索）后按遍历顺序得到的一个树状结构。对于有向图和无向图产生的 DFS 生成树是不同的，下面会对于有向图和无向图分别进行讲解。
有向图的 DFS 生成树
考虑这张图的 DFS 生成树：
有向图的 DFS 生成树中的边可以分为四类：
- 树边：在图中以黑色边表示。当 DFS 到一个未被访问过的结点时便形成了一个树边。
- 返祖边：在图中以红色边表示。在 DFS 过程中指向到祖先结点形成的边。
- 前向边：在图中以黄绿色边表示。在 DFS 过程中指向子树中结点形成的边。
- 横叉边：在图中以蓝色边表示。在 DFS 过程中指向一个与之不存在祖孙关系的边。
在 Tarjan 算法的流程中，前向边和横叉边都是没啥用的，所以一般将边分为树边和非树边就好了。
无向图的 DFS 生成树
考虑这张图的 DFS 生成树：
无向图的 DFS 生成树只有两类边：
- 树边：在图中以黑色边表示。当 DFS 到一个未被访问过的结点时便形成了一个树边。
- 后向边：在图中以黄绿色边表示。在 DFS 过程中连接祖先结点的边。
:::warning[为什么不存在横叉边？]
假设存在横叉边 (u,v)。不妨设 v 先于 u 被访问。
| 那么这时 v 一定会在自己的 DFS 过程中访问到 u，此时 u 会成为 v 的子孙结点，与横叉边的定义矛盾。 |
强连通分量
一个有向图强连通的充要条件是图中任意两个结点连通。
强连通分量（Strongly Connected Component，简称 SCC）是指一个极大的强连通子图。换句话说，如果一个图中的一个子图强连通，且再加入图中的任何一个外部结点都会使该子图不再强连通，那么这个子图是原图的一个强连通分量。
:::info[举个栗子]
双连通分量
双连通分为边双连通和点双连通。
在一个无向图中，若对于两个点，删去图中任意一条边都无法使其不连通，则这两个点边双连通。
同理，在一个无向图中，若对于两个点，删去图中任意一个点都无法使其不连通，则这两个点点双连通。
与强连通分量类似的，有：
- 边双连通分量（Edge-Biconnected Component，简称 e-BCC）是一个极大的边双连通子图。
- 点双连通分量（Vertex-Biconnected Component，简称 v-BCC）是一个极大的点双连通子图。
:::info[再举个栗子]
注意对于第二个图，点 4 实际上是被 \mathtt{v-BCC ~1} 和 \mathtt{v-BCC~2} 包含的，但是由于画图软件局限性无法展示。也因为这个原因，点 9 实际上是被 \mathtt{v-BCC ~2}、\mathtt{v-BCC~3} 和 \mathtt{v-BCC~4} 包含的。
| 同时，标红的点/边分别为这个图的割点/割边。关于割点和割边的定义见下一部分。 |
:::info[关于简称的补充说明]
也有一些人叫双连通分量 Double Connected Component，简称 DCC。在这篇文章中会称双连通分量为 BCC，只需要知道这两个是同个东西就好了。
:::
割点 & 割边
对于一个无向图，如果删掉一个点后图中的连通分量数增加了，那么这个点就是这个图的割点。
对于一个无向图，如果删掉一条边后图中的连通分量数增加了，那么这条边就是这个图的割边。
栗子在双连通分量的部分。
圆方树
圆方树是一种将一般无向图转化为一颗树的方法。
在一个圆方树中，每个结点是一个圆点或者方点；原图中的每一个点都是一个圆点，而圆方树中每一个方点代表着原图的一个点双连通分量。每个圆点都会连向其所在的点双对应的方点。特别的，一个割点会连向包含它的所有点双对应的方点。
:::info[举个栗子]
Tarjan 算法
连通性方面的 Tarjan 算法主要用于求出一个图的各种连通分量。对于要求解的内容，Tarjan 算法会有一定的区别。也是因为这个原因，只会在“求强连通分量”这一部分对 Tarjan 算法进行全面的讲解。请一定不要跳过“求强连通分量”这一部分。
在下面的解释中，定义 \mathtt{dfn}_u 表示深度优先搜索时结点 u 是第几个被访问的结点。同时，定义 \mathtt{low}_u 表示从点 u 或者 u 子树中的结点出发，通过至多一条非树边能到达的 \mathtt{dfn} 最小的祖先结点。
同时，如果这是无向图，在维护 \mathtt{low} 的时候不能从来时的边转移，因为不能原路返回。
:::info[举个栗子]
| 对于这个图，\mathtt{low}_3=1，因为可以通过 3\to 10\to 6\to 1 来到点 1。 |
| :::warning[为什么要定义为至多只能通过一条非树边？] |
| 首先我们要理解 \mathtt{low} 的目的。\mathtt{low} 数组的唯一目的就是判断某个结点是否为其所在连通分量中最早被访问的结点。这时候，仅通过一条非树边便可以保证 u 不是这个连通分量最早被访问的结点。 |
而对于无向图，如果允许经过多条非树边是会出现问题的，因为一个割点会属于多个点双连通分量，跳多次就可能会通过割点跳到另一个点双连通分量去。
考虑下面这个图：
| 结点 5,6,7 为一个点双连通分量。但是如果允许通过多条非树边，那么 \mathtt{low}_7=1，就会认为这整个图为一个点双连通分量。这显然是不对的。 |
求强连通分量
求强连通分量的过程中，会维护一个栈表示还没有确定其所在强连通分量的点，把搜索到的结点入栈。
容易发现 $\mathtt{dfn}_u \ge \mathtt{low}_u$。
:::warning[为什么只有在还没有确定其所在的强连通分量才更新呢？]
因为存在横叉边这个东西，不能通过跨 SCC 的边来更新 $\mathtt{low}$。
也因为这个原因后续求双连通分量的时候不需要考虑这个，毕竟没有横叉边嘛。
:::
下面会通过一些性质来解释 Tarjan 算法的运行流程。
> 性质 $1$：对于任意一个 SCC，其所有结点一定在其**第一个被访问**的结点 $u$ 的子树内。
:::info[证明]
由 SCC 的定义，由 $u$ 可以达到该 SCC 内所有结点。又因为 SCC 内其他结点晚于 $u$ 被访问，$u$ 一定会访问这个 SCC 内的所有其他结点，使其包含在 $u$ 的子树内。
:::
这启示我们，可以在每个 SCC 第一个被访问的结点统计这个 SCC。
那么，要怎么样找到这样的结点呢？
> 性质 $2$：结点 $u$ 是其所属的 SCC 中第一个被访问的结点的**充要条件**是 $\mathtt{dfn}_u=\mathtt{low}_u$。
:::info[证明]
先证明必要性：
反证法。假设 $\mathtt{low}_u<\mathtt{dfn}_u$，那么 $u$ 的子树内存在一条非树边可以到达某个比 $u$ 早入栈的点。此时这个点便与 $u$ 形成了一个环，即这两个点属于同一个 SCC，与 $u$ 为其所在 SCC 中首个被访问的元素矛盾。
再证明充分性：
若 $\mathtt{dfn}_u=\mathtt{low}_u$ 说明以 $u$ 为根的子树内无法到达 $u$ 上方的结点。也就是说 $u$ 的祖先结点与 $u$ 的子树不在同一个 SCC 内。因此 $u$ 一定是其所在 SCC 内第一个被访问的结点。
:::
找到这个结点后，意味着这个 SCC 内的所有结点都在栈内，就可以把 $u$ 所在的 SCC 的所有元素出栈并统计了。
如何找到与 $u$ 在同一个 SCC 的所有点呢？
> 性质 $3$：在处理完 $u$ 的整个子树后，点 $u$ 所属的 SCC 的所有结点**一定**在栈顶与 $u$ 栈内的位置之间，且栈顶与 $u$ 之间**仅有** $u$ 所属的 SCC 的结点。
:::info[证明]
先证明强连通性。
- 由于比 $u$ 晚入栈的结点 $v$ 一定在 $u$ 的子树内，所以从 $u$ 可以达到 $v$。
- 若某个 $u$ 子树内的结点 $v$ 无法到达 $u$，则 $\mathtt{low}_v=\mathtt{dfn}_v$，在从 $u$ 回溯时已经出栈，矛盾。所以从 $v$ 可以到达 $u$。
故栈顶到 $u$ 的所有元素强连通。
再证明极大性。假设存在一个不在栈内的结点 $w$，使得 $w$ 与 $u$ 强连通。
- 若 $\mathtt{dfn}_w<\mathtt{dfn}_u$，由强连通的定义可知能从 $u$ 到达 $w$。则 $\mathtt{low}_u \le \mathtt{dfn}_w < \mathtt{dfn}_u$，这与 $\mathtt{dfn}_u = \mathtt{low}_u$ 矛盾。
- 若 $\mathtt{dfn}_w>\mathtt{dfn}_u$ 且 $w$ 已经出栈，则 $u$ 和 $w$ 在同一个强连通分量内，而 $u$ 未出栈，矛盾。
综上所述，栈顶与 $u$ 之间包含且仅包含 $u$ 所在的 SCC 的所有结点。
:::
所以一直将栈顶出栈直到栈顶为 $u$ 就好了！
那么这就是 Tarjan 求强连通分量的完整流程了。
:::success[Code]
```cpp
int low[N],dfn[N],dfncnt;
int scc[N],sz[N],scccnt; //每个点所属的强连通分量编号，每个强连通分量大小，强连通分量个数
stack<int> st; //栈，维护未被归为一个 SCC 的点
bool in[N]; //是否在栈内
vector<int> g[N]; //这里使用邻接表存图
void tarjan(int u){
low[u]=dfn[u]=++dfncnt; //初始化
st.push(u); //入栈
in[u]=1;
for(auto v:g[u]){ //遍历图
if(!dfn[v]){ //没有被标号说明未被访问过
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(in[v]){
low[u]=min(low[u],dfn[v]); //只能经过至多一条非树边
}
}
if(dfn[u]==low[u]){ //是这个 SCC 的代表结点
scccnt++;
while(1){
int v=st.top();
st.pop();
in[v]=0; //出栈
scc[v]=scccnt;
sz[scccnt]++; //统计强连通分量
if(u==v) break; //如果当前出栈的元素是 u 那么整个 SCC 就已经求出来了
}
}
}
```
:::
## 求双连通分量
双连通分量分为点双连通分量和边双连通分量，下面会分别进行说明。
### 求边双连通分量
求边双连通分量的方法与求强连通分量的方法是基本没有区别的。
> 性质 $1$：若点 $u$ 满足 $\mathtt{low}_u=\mathtt{dfn}_u$ 且 $u$ 不是 DFS 树的根节点，那么连接 $u$ 和其父节点的边必为原图的割边。
:::info[证明]
若 $\mathtt{low}_u=\mathtt{dfn}_u$ 说明无法从 $u$ 通过非树边来到 $u$ 的祖先节点。那么 $u$ 与其父亲不边双连通，即这是一条割边。
:::
所以可以沿用求强连通分量的方法。
注意两点：
- 通过已经访问了的结点更新 $\mathtt{low}$ 就不需要判断是否在栈内了。原因可以看强连通分量部分的黄色折叠框。
:::warning[但是如果图有重边呢？]
如果这个图里面有重边就可以往回走了。
可以想到记录是否出现了重边。一种实现方法是在遇到一个指向父亲的边时将记录的父亲结点修改为 $0$，这时候后续的重边都会被认为是一个后向边。
:::
:::success[Code]
```cpp
int low[N],dfn[N],dfncnt;
int bcc[N],sz[N],bcccnt;
stack<int> st;
vector<int> g[N];
void tarjan(int u,int fa){ // 存父亲结点编号
low[u]=dfn[u]=++dfncnt;
st.push(u);
for(auto v:g[u]){
if(v==fa){
fa=0; // 处理重边的情况
continue;
}
if(!dfn[v]){
tarjan(v,u);
low[u]=min(low[u],low[v]);
}
else{ //这里就不需要判断是否在栈内了
low[u]=min(low[u],dfn[v]);
}
}
if(dfn[u]==low[u]){
bcccnt++;
while(1){
int v=st.top();
st.pop();
bcc[v]=bcccnt;
sz[bcccnt]++;
if(u==v) break;
}
}
}
```
:::
### 求点双连通分量
求点双连通分量可以沿用求边双连通分量的方法，但是由于一个割点同时属于多个点双连通分量，所以是通过某个割点和这个割点的儿子的子树来判断点双的。
令点 $u$ 为其点双连通分量中第一个被访问的结点，即 $\mathtt{dfn}$ 最小的结点。
> 性质 $1$：对于节点 $u$ 的某个子节点 $v$，以 $u$ 和 DFS 栈中 $v$ 及其以上的节点构成一个点双连通分量的**充要条件**是 $\mathtt{low}_v \ge \mathtt{dfn}_u$。
:::info[证明]
先证明充分性。
如果 $\mathtt{low}_v \ge \mathtt{dfn}_u$，意味着结点 $v$ 无法通过非树边来到 $u$ 的祖先结点。这意味这如果删除 $u$，$v$ 的整个子树就与原图不连通。因此，$u$ 与 $v$ 的子树构成了一个点双连通分量。
再证明必要性。
反证法。如果 $u$ 与 $v$ 的子树构成了一个强连通分量且 $\mathtt{low}_v < \mathtt{dfn}_u$，那么 $v$ 就可以通过某个不经过 $(u,v)$ 这条边的路径来到 $u$ 的祖先结点处。这样子这个祖先结点与 $v$ 属于同一个点双连通分量，与 $u$ 是该点双连通分量 $\mathtt{dfn}$ 最小的结点矛盾。
:::
所以我们判断一个 v-BCC 的依据是 $\mathtt{low}_v \ge \mathtt{dfn}_u$。
> 性质 $2$：当满足 $\mathtt{low}_v \ge \mathtt{dfn}_u$ 时，该点双连通分量在栈内的节点恰好为栈顶到 $v$ 的所有节点以及 $u$。
这个的证明方式与求 SCC 时的证明方式是类似的，在此不做赘述。
:::warning[为什么不能把 $u$ 和 $v$ 的子树内结点统一处理？]
因为 $u$ 是原图的割点，属于多个 v-BCC，应当保留在栈内。
:::
那么在发现 $\mathtt{low}_v \ge \mathtt{dfn}_u$ 后，便可以一直弹栈直到弹出 $v$，然后把弹出的所有元素和 $u$ 加入一个 v-BCC。同时，注意特判没有连边的结点。
:::success[Code]
```cpp
int low[N],dfn[N],dfncnt;
int bcccnt;
vector<int> bcc[N]; // 储存每个点双的所有结点
stack<int> st;
vector<int> g[N];
void tarjan(int u,int fa){
low[u]=dfn[u]=++dfncnt;
st.push(u);
for(auto v:g[u]){
if(v==fa){
continue;
}
if(!dfn[v]){
tarjan(v,u);
low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u]){ // 对每一个子树分别判断是否为一个点双
bcccnt++;
while(1){
int w=st.top();
st.pop();
bcc[bcccnt].push_back(w);
if(v==w) break;
}
bcc[bcccnt].push_back(u); // 把割点也加入这个点双
}
}
else{
low[u]=min(low[u],dfn[v]);
}
}
if(fa==-1&&g[u].empty()){ // 特判单一结点
bcccnt++;
bcc[bcccnt].push_back(u);
st.pop();
}
}
```
:::
## 求割点 & 割边
分为求割点和割边。
### 求割点
发现在求点双的过程中，$\mathtt{low}_v \ge \mathtt{dfn}_u$ 就得出了 $u$ 是一个割点。这时候就不需要维护一个栈了，因为找出这个割点已经足够了。
同时需要注意一下根节点需要有至少两个儿子才为一个割点。
剩下的用求点双的方法就好了。
:::success[Code]
```cpp
int low[N],dfn[N],dfncnt;
bool iscut[N]; // 每个结点是否为一个割点
int cutcnt; // 割点数量
vector<int> g[N];
void tarjan(int u,int fa){
low[u]=dfn[u]=++dfncnt;
int child=0;
for(auto v:g[u]){
if(v==fa){
continue;
}
if(!dfn[v]){
child++;
tarjan(v,u);
low[u]=min(low[u],low[v]);
if(fa!=-1 && low[v]>=dfn[u] && !iscut[u] /*避免重复算*/){
iscut[u]=1;
cutcnt++;
}
}
else{
low[u]=min(low[u],dfn[v]);
}
}
if(fa==-1 && child>=2 && !iscut[u]){
iscut[u]=1;
cutcnt++;
}
}
```
:::
### 求割边
> 性质 $1$：在 $u$ 为 $v$ 的父节点时，$(u,v)$ 是割边的**充要条件**是 $\mathtt{low}_v>\mathtt{dfn}_u$。
:::info[证明]
先证明充分性：
$\mathtt{low}_v>\mathtt{dfn}_u$ 意味着无法在经过 $(u,v)$ 这条边的前提下从以 $v$ 为根的子树到达 $u$ 或者 $u$ 的祖先结点。那么在删除 $(u,v)$ 这条边后 $v$ 及其子树便与原图不连通了。因此 $(u,v)$ 为一个割边。
再证明必要性：
反证法。假设 $(u,v)$ 是一条割边而且 $\mathtt{low}_v\le\mathtt{dfn}_u$。这意味着还有一个非树边可以来到 $u$ 或者 $u$ 的祖先。在删除 $(u,v)$ 后 $v$ 及其子树仍然和原图连通，与 $(u,v)$ 为一条割边矛盾。
:::
所以在 $\mathtt{low}_v>\mathtt{dfn}_u$ 的时候，这条边就是原图的一个割边。注意处理重边，剩下的就和求点双是一样的了。
:::success[Code]
```cpp
int low[N],dfn[N],dfncnt;
bool iscut[M]; // 每个边是否为一个割边
int cutcnt; // 割边数量
struct Edge{
int v,id;
};
vector<Edge> g[N];
void tarjan(int u,int eg /*来时的边的编号*/){
low[u]=dfn[u]=++dfncnt;
for(auto e:g[u]){
int v=e.v,id=e.id;
if(id==eg){
continue;
}
if(!dfn[v]){
tarjan(v,id);
low[u]=min(low[u],low[v]);
if(low[v]>dfn[u] && !iscut[id] /*避免重复算*/){
iscut[id]=1;
cutcnt++;
}
}
else{
low[u]=min(low[u],dfn[v]);
}
}
}
```
:::
## 时间复杂度
由于 Tarjan 算法会对原图进行一次 DFS 遍历，时间复杂度为 $\mathcal{O}(n+m)$。
# 应用
正如前言所说，求出连通分量之后的主要用处是**缩点**。进行缩点之后整个图就没有环了，多了很多优秀的性质。下面会给出一些例题进行讲解。
## SCC 缩点
### [P3387 【模板】缩点 / 强连通分量](/problem/P3387)
考虑 dp。设计 $f_u$ 表示从起点到点 $u$ 可以获得的最大收益。但是现在这个图有环，转移会有后效性。
可以想到对于一个 SCC 中的结点，由于可以访问整个 SCC 再回到原点，所以可以免费获得整个 SCC 的收益。这时候便可以把整个 SCC 替换为一个保留了所有原本 SCC 中的出边，权值为 SCC 内所有结点之和的新点。
> 性质：对所有 SCC 缩点后的图没有环，即缩点后的图为一个 DAG。
:::info[证明]
反证法。假设缩点后的图有环，那么这个环的所有结点都可以互相到达，即这是一个 SCC，矛盾。
:::
也就是说缩点后的图就不会有后效性了。转移方程为：
$$f_u=\max_{(u,v)\in E} \big(f_v+a_v\big)$$
:::success[Code]
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e4+5;
int n,m,dfncnt,scccnt;
int low[N],dfn[N],scc[N],sz[N],out[N],f[N],a[N],val[N],vis[N];
bool in[N];
stack<int> st;
vector<int> g[N],h[N];
void tarjan(int u){
low[u]=dfn[u]=++dfncnt;
st.push(u);
in[u]=1;
for(auto v:g[u]){
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(in[v]){
low[u]=min(low[u],dfn[v]);
}
}
if(dfn[u]==low[u]){
scccnt++;
while(1){
int v=st.top();
st.pop();
in[v]=0;
scc[v]=scccnt;
sz[scccnt]++;
val[scccnt]+=a[v]; // 统计这个 SCC 代表的点的权值和
if(u==v) break;
}
}
}
int dp(int u){ // 使用记忆化搜索实现 dp 转移
if(vis[u]){
return f[u];
}
vis[u]=1;
int mx=0;
for(auto v:h[u]){
mx=max(mx,dp(v));
}
return f[u]=val[u]+mx;
}
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
g[u].push_back(v);
}
for(int i=1;i<=n;i++){
if(!dfn[i]){
tarjan(i); //图可能不连通，要对所有连通块做一遍 Tarjan
}
}
for(int u=1;u<=n;u++){
for(auto v:g[u]){
if(scc[u]!=scc[v]){
h[scc[u]].push_back(scc[v]); //缩点
}
}
}
int ans=0;
for(int i=1;i<=scccnt;i++){
ans=max(ans,dp(i));
}
cout<<ans;
return 0;
}
```
:::
### [P2341 [USACO03FALL / HAOI2006] 受欢迎的牛 G](/problem/P2341)
首先一个 SCC 里面的所有奶牛都是互相喜欢的，可以缩点缩成一个 DAG。这个 DAG 内如果仅存在一个出度为 $0$ 的点，那么这个点（或者这个点所代表的 SCC）就是明星。如果有多个出度为 $0$ 的点，这个图里面就没有明星了。
:::success[Code]
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e4+5;
int n,m,dfncnt,scccnt;
int low[N],dfn[N],scc[N],sz[N],out[N];
bool in[N];
stack<int> st;
vector<int> g[N];
void tarjan(int u){
low[u]=dfn[u]=++dfncnt;
st.push(u);
in[u]=1;
for(auto v:g[u]){
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(in[v]){
low[u]=min(low[u],dfn[v]);
}
}
if(dfn[u]==low[u]){
scccnt++;
while(1){
int v=st.top();
st.pop();
in[v]=0;
scc[v]=scccnt;
sz[scccnt]++;
if(u==v) break;
}
}
}
signed main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
g[u].push_back(v);
}
for(int i=1;i<=n;i++){
if(!dfn[i]){
tarjan(i);
}
}
for(int u=1;u<=n;u++){
for(auto v:g[u]){
if(scc[u]!=scc[v]){
out[scc[u]]++; //统计缩点后每个 SCC 代表的点的度数
}
}
}
int cnt=0,ans=0;
for(int i=1;i<=scccnt;i++){
if(!out[i]){
cnt++;
ans=sz[i];
}
}
if(cnt==1) cout<<ans;
else cout<<0;
return 0;
}
```
:::
## 边双缩点
### [P2860 [USACO06JAN] Redundant Paths G](/problem/P2860)
首先对原图的边双缩点。
> 性质：给所有 e-BCC 缩点后的图没有环，即缩点后的图为一棵树。
:::info[证明]
反证法。假设缩点后的图有环，那么这个环就是一个 e-BCC，矛盾。
:::
原题转化为给一颗树加上尽量少的边使其为一个边双连通图。
> 结论：对于一棵包含 $L$ 个叶子节点的树，要使其变为边双连通图，至少需要添加的边数为 $\left\lfloor \frac{L}{2} \right\rfloor$。
:::info[证明]
对于一个边双连通图，所有节点的度一定不小于 $2$。所有叶子节点的度都是 $1$，至少需要 $\left\lfloor \frac{L}{2} \right\rfloor$ 条边才能将所有叶子结点的度增加至少 $1$。
下面给出一种构造方法。
- 若 $L=2$，则直接给两个叶子节点连边，构造完毕。
- 若 $L>2$，选取树的重心为根，按 DFS 顺序将所有叶子节点编号为 $u_1,u_2,\dots,u_L$。
令 $k=\lfloor \frac{L}{2} \rfloor$。
- 若 $L \equiv 0 \pmod 2$，则连接 $(u_i,u_{i+k})~\big(1\le i \le k\big)$。
- 若 $L \equiv 1 \pmod 2$，则连接 $(u_i,u_{i+k})~\big(1\le i \le k\big)$，并额外连接 $(u_{L-k},u_{L})$。
接下来证明这个构造方法是正确的。
假设存在一条图上的边 $e$ 使得在删除 $e$ 后两个子树不连通。那么其中不含根节点的子树的所有叶子结点的 DFS 序为一个连续区间 $[a,b]$。
如果两个子树不连通，则所有的 $(u_i,u_{i+k})$ 都在同一个子树内。因为构成一个连续区间，这个区间的长度必定**严格大于** $k$。这意味着这个子树内的叶子节点数严格大于 $\frac{L}{2}$。
那么另一个子树的叶子结点数量严格小于 $\frac{L}{2}$，必定有某个叶子节点连向另一颗子树，矛盾。
综上所述，这个图是一个强连通图。
:::
那么答案就是 $\lfloor\frac{L}{2}\rfloor$。
:::success[Code]
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5005;
int low[N],dfn[N],dfncnt,f,r;
int bcc[N],sz[N],bcccnt,deg[N];
stack<int> st;
vector<int> g[N];
void tarjan(int u,int fa){
low[u]=dfn[u]=++dfncnt;
st.push(u);
for(auto v:g[u]){
if(v==fa){
fa=0;
continue;
}
if(!dfn[v]){
tarjan(v,u);
low[u]=min(low[u],low[v]);
}
else{
low[u]=min(low[u],dfn[v]);
}
}
if(dfn[u]==low[u]){
bcccnt++;
while(1){
int v=st.top();
st.pop();
bcc[v]=bcccnt;
sz[bcccnt]++;
if(u==v) break;
}
}
}
signed main(){
cin>>f>>r;
for(int i=0;i<r;i++){
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
tarjan(1,0);
for(int u=1;u<=f;u++){
for(auto v:g[u]){
if(bcc[u]!=bcc[v]){
deg[bcc[u]]++; // 只需判断是否为叶子结点，统计度数即可
}
}
}
int leaf=0;
for(int i=1;i<=bcccnt;i++){
if(deg[i]==1){ // 叶子节点的度为 1
leaf++;
}
}
cout<<(leaf+1)/2<<"\n";
return 0;
}
```
:::
## 点双缩点 / 圆方树
对无向图进行缩点其实就是对该图构建一个圆方树。
考虑求点双连通分量的算法。当 $\mathtt{low}_u\ge \mathtt{dfn}_v$ 时，栈中到 $v$ 之上的结点以及割点 $u$ 构成一个点双。那么，只需要新建一个方点，再将弹出的所有节点以及 $u$ 与这个方点连边即可。
圆方树有一些优秀的性质：
> 性质 $1$：圆方树是一个二分图，圆点仅连向方点，方点仅连向圆点。
> 性质 $2$：原图中 $u, v$ 两点间所有简单路径的并集，恰好对应圆方树上 $u,v$ 唯一简单路径所包含的所有圆点以及这些方点代表的点双连通分量中的所有圆点。
> 性质 $3$：原图中的割点在圆方树中的度数大于 $1$；所有非割点在圆方树中的度数等于 $1$（即为叶子节点）。
:::success[Code]
```cpp
int low[N],dfn[N],dfncnt;
int bcccnt;
stack<int> st;
vector<int> e[2*N]; //要存储方点，所以开两倍空间
vector<int> g[N]; //原图
void tarjan(int u,int fa){
low[u]=dfn[u]=++dfncnt;
st.push(u);
for(auto v:g[u]){
if(v==fa){
continue;
}
if(!dfn[v]){
tarjan(v,u);
low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u]){
bcccnt++;
while(1){
int w=st.top();
st.pop();
e[w].push_back(bcccnt+n);
e[bcccnt+n].push_back(w); //将方点与 BCC 中的点连边，方点编号为 bcccnt+n
if(v==w) break;
}
e[u].push_back(bcccnt+n); //将割点与方点连边
e[bcccnt+n].push_back(u);
}
}
else{
low[u]=min(low[u],dfn[v]);
}
}
if(fa==-1&&g[u].empty()){ //类似于点双的特判
bcccnt++;
e[u].push_back(bcccnt+n);
e[bcccnt+n].push_back(u);
st.pop();
}
}
```
:::
### [P4320 道路相遇](/problem/P4320)
发现题目要求的就是 $u,v$ 两点简单路径上的割点数量。
回想圆方树的定义，两个点双之间通过割点相连，所以考虑建出圆方树。
此时题目转为 $(u,v)$ 简单路径上圆点的数量，由于圆点仅与方点连接，方点仅与圆点连接，答案就是 $\lfloor \frac{\text{dis}(u,v)}{2}\rfloor$，其中 $\text{dis}(u,v)$ 表示 $u,v$ 间简单路径的距离。
:::success[Code]
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+10，M=20;
int n,m,q,tot,dfncnt,top;
int dfn[N],low[N],dep[2*N];
int up[2*N][M]; //倍增数组
vector<int> g[N],e[2*N];
int bcccnt;
stack<int> st;
void tarjan(int u,int fa){
low[u]=dfn[u]=++dfncnt;
st.push(u);
for(auto v:g[u]){
if(v==fa){
continue;
}
if(!dfn[v]){
tarjan(v,u);
low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u]){
bcccnt++;
while(1){
int w=st.top();
st.pop();
e[w].push_back(bcccnt+n);
e[bcccnt+n].push_back(w);
if(v==w) break;
}
e[u].push_back(bcccnt+n);
e[bcccnt+n].push_back(u);
}
}
else{
low[u]=min(low[u],dfn[v]);
}
}
if(fa==-1&&g[u].empty()){
bcccnt++;
e[u].push_back(bcccnt+n);
e[bcccnt+n].push_back(u);
st.pop();
}
}
void dfs(int u,int fa){
dep[u]=dep[fa]+1;
up[u][0]=fa;
for(int i=1;i<M;i++){
up[u][i]=up[up[u][i-1]][i-1];
}
for(int v:e[u]){
if(v!=fa){
dfs(v,u);
}
}
}
int lca(int u,int v){ //倍增求 LCA
if(dep[u]<dep[v]){
swap(u,v);
}
for(int i=M-1;i>=0;i--){
if(dep[u]-(1<<i)>=dep[v]){
u=up[u][i];
};
}
if(u==v){
return u;
}
for(int i=M-1;i>=0;i--){
if(up[u][i]!=up[v][i]){
u=up[u][i];
v=up[v][i];
}
}
return up[u][0];
}
signed main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
tarjan(1,-1);
dfs(1,0);
cin>>q;
while(q--){
int u,v;
cin>>u>>v;
int d=dep[u]+dep[v]-2*dep[lca(u,v)]; //树上两点间的距离
cout<<d/2+1<<'\n';
}
return 0;
}
```
:::
# 结语
[圆方树好文](/article/7xxcgud3)
[连通性相关题单](/training/248579)
至此，我们解释了 OI 中的强连通分量、双连通分量相关内容以及通过 Tarjan 求连通分量的方法以及原理。
如果您认为文章哪里存在问题或理解不当，欢迎在评论区指出或者私信作者。感谢您的阅读。
:::info[鸣谢]
感谢 @[clx201022](/user/552688) 为本文提供修改意见，关注 @[clx201022](/user/552688) 谢谢喵！
感谢 @[__Eric123](/user/1403446) 提供精神支持（？），关注 @[__Eric123](/user/1403446) 谢谢喵！
感谢 OI-wiki 和 Gemini 提供参考资料。
:::