双联通分量(Tarjan)

cloud2764scallop_eve · 2023-10-17 21:10:59 · 算法·理论

前言：有个问题，为什么Bing搜索的第一页的博客基本上都一样？

前置芝士

割点和桥

基本定义/性质

在一个无向图中，若任意两点间至少存在两条点不重复的路径，则说这个图是点双连通的（简称双连通，\text{biconnected}）。

对于以上的定义，存在一种特殊情况，即无向图 G 中只存在两个点和一条联通的边。这样的图符合定义，所以以上性质只适用于绝大多数情况。

在一个无向图中，点双连通的极大子图称为点双连通分量（简称双连通分量，\text{Biconnected Component,BCC}）。

性质

不太理解用途，但是好像非常有用，经常被提及，所以记录一下。

任意两点间至少存在两条点不重复的路径等价于图中删去任意一个点都不会改变图的连通性，即 \text{BCC} 中无割点。
若 \text{BCC} 间有公共点，则公共点为原图的割点。
无向连通图中割点一定属于至少两个 \text{BCC}，非割点只属于一个 \text{BCC}。

点双连通分量

只在无向图中讨论。

定义

在一张连通的无向图中，对于两个点 u 和 v，如果无论删去哪个点（只能删去一个，且不能删 u 和 v 自己）都不能使它们不连通，我们就说 u 和 v 点双连通。 ——\text{OI-Wiki}

即若一个无向图中的去掉任意一个节点都不会改变此图的连通性，即不存在割点，则称作点双连通图。

性质

点双连通不具有传递性，反例如下图，A,B 点双连通，B,C 点双连通，而 A,C 不点双连通。

该连通分量的点在同一简单环。
该连通分量没有桥。
一个割点可以多个点连通分量。
求解

老朋友 \text{DFS} 和 \text{Tarjan} 了。
无向连通图中割点一定属于至少两个 \text{BCC} ，非割点只属于一个 \text{BCC} 。
到一个结点就将该结点入栈，回溯时若目标结点 low 值不小于当前结点 dfn 值就出栈直到目标结点（目标结点也出栈），将出栈结点和当前结点存入 \text{BCC} 。对于每个 \text{BCC}，它在 \text{DFS} 树中最先被发现的点一定是割点或DFS树的树根。
等效于：每个 \text{BCC} 都在其最先被发现的点（一个割点或树根）的子树中。
这样每发现一个 \text{BCC}（low_v \ge dfn_u），就将该子树出栈，并将该子树和当前结点（割点或树根）加入 \text{BCC} 中。上面的操作与此描述等价。

代码
```
void tarjan(int u, int fa) {
low[u] = dfn[u] = ++Time;
st[++Top] = u; //依次进栈
for (int i = head[u]; i; i = e[i].next) {
    int v = e[i].to;
    if (!dfn[v]) {
        tarjan(v, u);
        low[u] = min(low[u], low[v]);
        if (dfn[u] <= low[v]) { //如果u为割点，点双缩点
            ++num; //num表示第几个点双区域(一个图可能存在多个点双)
            while (st[top + 1] != v) { //从栈顶到v依次出栈
                int w = s[top--]; //去栈顶并退栈
                dcc[num].push_back(w);//节点v属于编号为num的点双
            }
            dcc[num].push_back(u);//u可以在多个bcc，所以不出栈
        }
    } else if (v != fa)
        low[u] = min(low[u], dfn[v]);
}
}
```

贴上 \text{OI-Wiki} 的解法，我没有太理解。

\text{DFS} 找割点并判断点双连通

如上图所示，黑色边为树边，红色边为非树边。每一条非树边连接的两个点都对应了树上的一条简单路径。
考虑一张新图，新图中的每一个点对应原图中的每一条树边（在上图中用蓝色点表示）。对于原图中的每一条非树边，将这条非树边对应的树上简单路径中的所有边在新图中对应的蓝点连成一个连通块（这在上图中也用蓝色的边体现出来了）。
这样，一个点不是割点，当且仅当与其相连的所有边在新图中对应的蓝点都属于同一个连通块。两个点点双连通，当且仅当它们在原图的树上路径中的所有边在新图中对应的蓝点都属于同一个连通块。
蓝点间的连通关系可以用与求边双连通时用到的差分类似的方法维护，时间复杂度 O(n+m)。

边双连通分量

同点双连通分量，只在无向图中讨论。

定义

在一张连通的无向图中，对于两个点 u 和 v，如果无论删去哪条边（只能删去一条）都不能使它们不连通，我们就说 u 和 v 边双连通。 ——\text{OI-Wiki}

若一个无向图中的去掉任意一条边都不会改变此图的连通性，即不存在桥，则称作边双连通图。

性质

不同于点双连通分量，边双连通具有传递性，即，若 x,y 边双连通，y,z 边双连通，则 x,z 边双连通。

任意一条边至少包含在一个简单环。
连通分量里没有桥。
割点只属于一个边双连通分量。

两个边双连通分量最多只有一条边，且必为桥。进一步地，所有边双连通分量与桥可抽象为一棵树结构。

求解

类似于点双连通分量，不做详细解释。
边双连通分量里，一个点有可能出现在多个简单环里，所以我们在当前点u的所有子树访问结束，即变黑后，如果 dfn[u]==low[u]，从栈顶到 u 的点均为同一边双连通分量，节点 u 必然是此边双的最早访问的点。

代码


void tarjan(int u, int fa) {
bool flag = 0; //是否有重边
low[u] = dfn[u] = ++Time;
st[++Top] = u; //依次进栈
for (int i = head[u]; i; i = e[i].next) {
    int v = e[i].to;
    if (!dfn[v]) { //白点
        tarjan(v, u);
        low[u] = min(low[u], low[v]); //儿子更新父亲
    } else if (v != fa)
        low[u] = min(low[u], dfn[v]);
}  //u的子树全部访问结束，边双缩点
if (low[u] == dfn[u]) {
    num++;
    int tmp;
    do {
        tmp = st[Top--]; //退栈,原来栈中的元素构成一个边双
        belong[tmp] = num;
    } while (tmp != u);
}



同样，贴上没太看懂的 $\text{OI-Wiki}$ 的解法。
## $\text{DFS}$ 找桥并判断边双连通
首先，对原图进行 $\text{DFS}$。  
![](https://oi-wiki.org/graph/images/bcc-1.svg)  
如上图所示，黑色与绿色边为树边，红色边为非树边。每一条非树边连接的两个点都对应了树上的一条简单路径，我们说这条非树边 **覆盖** 了这条树上路径上所有的边。绿色的树边 **至少** 被一条非树边覆盖，黑色的树边 **不** 被任何非树边覆盖。  
我们如何判断一条边是不是桥呢？显然，非树边和绿色的树边一定不是桥，黑色的树边一定是桥。  
如何用算法去实现以上过程呢？首先有一个比较暴力的做法，对于每一条非树边，都逐个地将它覆盖的每一条树边置成绿色，这样的时间复杂度为 $O(nm)$。  
怎么优化呢？可以用差分。对于每一条非树边，在其树上深度较小的点处打上 $-1$ 标记，在其树上深度较大的点处打上 $+1$ 标记。然后 $O(n)$ 求出每个点的子树内部的标记之和。对于一个点 $u$，其子树内部的标记之和等于覆盖了 $u$ 和 $u$ 的父亲之间的树边的非树边数量。若这个值非 $0$，则 $u$ 和 $u$ 的父亲之间的树边不是桥，否则是桥。  
用以上的方法 $O(n+m)$ 求出每条边分别是否是桥后，两个点是边双连通的，当且仅当它们的树上路径中 **不** 包含桥。  
# 应用（模型）
## 加边
有一些点，一些边，加最少的边，要使得整个图变成双联通图。
### 思路
如果是连通图，先缩点，建图，新图为一颗树，求出叶子节点个数 $cnt$，最后答案为 `(cnt+1)/2`。  
如果是非连通图，缩点后，先把单点连起来，再来就算叶子个数，或把单点算两个叶子。
## 求必经点
连通图，给一个起点和一个终点，问从起点到终点的必经点。
### 思路
点双连通分量缩点，然后建成树，起点到终点路径上点均为必经点。  

## 参考
[Tarjan算法求双连通分量](https://www.cnblogs.com/hbhszxyb/p/12812434.html)  
[双连通分量（点-双连通分量&边-双连通分量）](https://www.cnblogs.com/jiamian/p/11202189.html)（[双连通分量（点-双连通分量&边-双连通分量）](https://www.cnblogs.com/DWVictor/p/11348042.html)《基本》完全相同的一篇博客，前面的大抵是原创，不确定）  
[[算法笔记] 双连通分量](https://www.cnblogs.com/IltzInstallBI/p/13113566.html)  
[点双连通分量&边双联通分量详解](https://blog.csdn.net/a_forever_dream/article/details/103019013)  
[双连通分量 - OI Wiki](https://oi-wiki.org/graph/bcc)