无向图的割点，割边，双连通分量

[[ slider_text ]]

[[ item.c ]]

无向图的割点，割边，双连通分量

发布时间 2024-05-01 作者：秋千月 来源：算法小站，OI-WIKI

树上问题 图的连通性 树形dp 双连通分量 圆方树

## 无向连通图的相关概念
### 割点割边的定义
**割点**，无向连通图中，删除这个点之后，图分成了不连通的两个部分
**割边**，无向连通图中，删除这条边后，图分成了不连通的两个部分

### 双连通分量
**点双连通**，没有割点
**边双连通**，没有割边
换句话说，要把点双（边双）的图，切成不连通的两部分，要删除$$\geqslant 2$$个点（边）

**双连通有一些性质**
![](/media/content_img/dcc-example.png)
**点双**，存在两条不相交的简单路径
> 证明，如果`u, v`之间有割点，那么$$u \to v$$的路径会经过割点，和双连通矛盾

**边双**，有两条不经过重复边的路径，但路径上可能有割点

**双连通分量**
图中找一个极大的点集，满足其导出子图是点（边）双连通的
也就是说，再加入一个点，或者再接入一条边，就是非双连通的，也就是说**出现了割点或者桥**
（割边有时候又被称为桥）

> 这样似乎形成了一些思路？

求**边双**，找割边，然后把割边切掉，剩下的每个连通块都是边双
求**点双**，找到割点并删去，但每个割点可能在**多个点双连通分量中**

另外注意的是，每一条边都只会在一个边双中，在编程实现的时候，删点比删边容易些
求边双的时候，也可以先考虑删去割点，如果割点和不同的块连通，再将其加入相应的块中，这样大致形成了边双

### 双连通分量缩图
![](/media/content_img/dcc-condense.png)

先考虑边双，因为边双相对简单一些，一条只会在一个边双中，容易发现，边双缩图完，
是一棵树

> 如果还有环的话，那么这个环中的边都不是割边，大环上的点又会形成一个更大的双连通分量，矛盾了

点双比较难处理，因为**一个割点可能在多个点双中**，但缩点之后，也是类似树一样的结构
![](/media/content_img/dcc-condense-2.png)
点双的缩点，需要`2`步

*  每个点双新建一个点
*  这个新点（如图大写英文字母）和该点双中的所有点连边

## tarjan 算法求割边
### 算法思想
![](/media/content_img/tarjan-dcc-edge.png)
无向图的 dfs 树中，`ForwardEdge, CrossEdge`都不存在，只有`TreeEdge, BackEdge`
**仅存在树边，返祖边**

> 什么时候，一条边会成为割边？

首先，非树边一定不可能是割边，因为删除了之后不破坏`dfs`树的主干
割边就意味着，删了这条边之后，这条边往下的子树不能通过返祖边连回去了

Tarjan 算法用`low(u)`表示`u`能跳到`dfn`最小的点，割边只能是树边，求`low`的时候类似树形 dp

无向图中，要注意**重边**，所以`dfs`的时候，带上**编号**
```bash
dfs(u, id):
	dfn(u) = low(u) = ++idx
	for (v, id2) : G[u]:
		if (dfn(v) == 0):		dfs(v, id2)
		if (id != id2):		low(u) = min(low(u), low(v))
		
	if dfn(u) == low(u):		边 id 是 bridge
```

**特别说明**，`low(u) = min(low(u), low(v))`的写法，在求**割点**的时候，是不对的
因为这个等式是**树形dp**，当且仅当$$(u,v)$$是树边的时候成立，但如果是**返祖边**，会发生什么呢？
可能通过**返祖边**指向了**非常早的祖先**
```bash
如果 (u, v) 是返祖边
low(u) = min( low(u), low(v) )，此时
low(u) = ancestor，跳了多步
```

### 算法实现
无向图中，我们定义`low(u) = min(low(u), low(v))`是树形 dp，当且仅当$$(u,v)$$是树边时成立
这样割边的判定的代码可以写成
```bash
dfs(u, id):  id 表示前向弧
	dfn(u) = low(u) = ++idx
	
	for (v, id2) : G[u]:
		if (!dfn(v)):		(u, v) is TreeEdge
			dfs(v, id2),  low(u) = min( low(u), low(v) )
		else if (id != id2):  判断非重边，(u, v) is BackEdge
			low(u) = min( low(u), dfn(v) )
			
	if ( low(u) == dfn(u) AND id != -1 ):
		edge[id] is Bridge
		
in main:
	dfs(1, -1)
```
桥求出来之后，**边双连通分量**怎么求呢？可以用**强连通分量的方法**

```bash
function<void(int, int)> dfs = [&](int u, int id) -> void {
	dfn[u] = low[u] = ++idx;
	stk.push(u);

for (auto [v, id2] : G[u]) {
		if (!dfn[v]) {
			dfs(v, id2);
			low[u] = min(low[u], low[v]);
		}
		else if (id != id2) low[u] = min(low[u], dfn[v]);
	}
	
	if (low[u] == dfn[u]) {
		if (id != 0) bridge.push_back(id), isbridge[id] = 1;
		++cnt;
		while (true) {
			auto v = stk.top();
			stk.pop();
			edcc[cnt].push_back(v), bel[v] = cnt;
			if (v == u) break;
		}
	}
};
```

##  tarjan 算法求割点
### 算法思想
**割点**的定义，如下图所示
![](/media/content_img/cut-vertex.png)
**特别注意**，无向图中，`low(u)`表示`u`往上**只跳一步**能跳到的点，一般来说是沿着**树边**跳

注意割边和割点在算法思想上的区别，主要是**割点**的`low`不能随便乱写
![](/media/content_img/cut-vertex-low1.png)
对于割点来说，`low`随便写，可能导致往上跳多步，这是不对的
![](/media/content_img/cut-vertex-low2.png)

### 算法实现
* 要统计一下儿子的个数`ch`,`dfs(u, fa)`的时候，记一下`u`的儿子个数`ch`

* 割点，求的时候注意特判根节点，对于非根节点`u`，只要存在一个儿子`v`，满足$$low(v) \geqslant dfn(u)$$
  `u`就是割点
  
```bash
dfs(u, fa):
	let ch = 0
	
	for (v in G[u]):
		if (!dfn[v]):		TreeEdge
			dfs(v, u), ch++, low[u] = min( low(u), low(v) )
			if ( low(v) >= dfn(u) ):	u is Cut-Vertex
		else if (v != fa):	BackEdge
			low(u) = min( low(u), dfn(v) )
			
	if (u == 1 AND ch <= 1) u is root, not Cut-Vertex
	
in main:
	dfs(1, -1)
```

### Block Tree 缩点
dfs 的时候，用栈来**维护子树**

* 对于树边$$(u, v)$$，如果`dfs`到`u`的时候，`for u 的所有儿子`
  发现`u`的一个分支`v`，满足$$low(v) \geqslant dfn(u)$$，说明`v`这棵子树是一个以`u`为根的点双

* `cnt += 1`（`cnt`从`n+1`开始编号），表示发现了一个点双，新建一个点

*  将点双中的点`x`，除了`u`以外全部退栈，$$(x, cnt)$$连双向边
   `u`不退栈，但是$$(cnt, u)$$也需要连双向边
   
*  继续检查`u`的其他分支

注意到处理非连通图的时候，`dfs(i, -1)`，执行完之后，栈中还有一个元素，即根，也需要退栈

### Block Tree 例子
#### APIO 2018
**[APIO 2018 铁人两项](https://www.luogu.com.cn/problem/P4630)**
**问题描述**，给定一张简单无向图，问有多少对三元组$$(s, c, f)$$，其中$$s, c, f$$互不相同
满足条件，使得存在一条简单路径从$$s$$出发，经过$$c$$到达$$f$$

**算法分析**
> 这种问题一般是怎么做的？

这种问题思路比较固定，可以**枚举**`c`，然后考虑在**一个分支**里选`s`，能选几个？$$sz(s)$$个
再另一个分支里选`f`，能选几个？$$sz(f)$$个
这样答案就是 $$\sum sz(f) \cdot sz(s)$$

```bash
for 每一个点 c:
	for c 的每一个儿子 x：		计数
```
计数 $$\sum_{x \in son(c)} sz(x) \cdot \left( sz(c) - sz(x) - 1 \right)$$

注意到这样做时间复杂度是$$O(n^2)$$的，将时间复杂度降低下来的方法，考虑**二次扫描和换根**

![](/media/content_img/changeroot-01.png)
![](/media/content_img/changeroot-02.png)

这样，基于以上分析，`dfs(c)`的时候，可以顺便进行计数
只需要考虑，在哪个区域里选$$s$$，剩下能选的$$f$$也确定了，注意到能够选择的点一共是
$$tot = sz(c) + \overline{sz}(c) - 1$$（扣除$$c$$这个点本身）

如果在$$\overline{sz}(c)$$区域选择点$$s$$，那么$$f$$只能在$$sz(c)$$区域了
$$ans += \overline{sz}(c) \cdot (tot - \overline{sz}(c))$$

否则，考虑一边`dfs, for c 的所有儿子 x`，如果$$s$$在$$sz(x)$$中，那么$$ans += sz(x) \cdot (tot - sz(x))$$

> 这样做是否是对的呢？是否不重不漏呢？

上述的分析，对于树的情况，是正确的，但题目给的是无向图，也就是说可能还会有若干个环
换句话说，$$\left<c, sz(c), \overline{sz}(c) \right>$$三个部分可能在一个连通块中，那这时候怎么办呢？
可以考虑，将图的情况转化为树的情况，也就是说，**对点双缩点，考虑圆方树（Block Tree）**

>  **圆方树的性质**
   *  方点之间不会连边，并且任意一条简单路径上，圆点和方点间隔分布
>   
   *  一般情况下，记圆点的`size = 1`，方点的`size = 0`（方点实际上是虚拟的点）
      圆点子树的`size`和就是它下面的所有点的数量
>	  
   *  点双中，任意两个点，它们之间简单路径的并集，恰好等于这个点双。同一个点双中的两个不同点$$(u, v)$$
      一定存在一条简单路径，经过同一点双中的另一个点$$w$$
	  换句话说，在圆方树中找两个点$$u, v$$，考虑$$u, v$$的路径，一定经过若干个方点
	  单独看这些方点，和这些方点相邻的圆点的集合，恰好等于原图上$$u, v$$两点简单路径上的点集
>
   * 割点有一些很好的性质，割点的$$\text{deg} \geqslant 2$$，同时割点一定是圆点，且和方点相邻
   和方点相邻，并且$$\text{deg} \geqslant 2$$的圆点也一定是割点
   非割点，那么它一定是叶子结点，也就是说$$\text{deg} = 1$$
   方点必不可能是叶子结点
   
根据圆方树的性质分析，在**之前的讨论**中，我们考虑了$$c$$为**圆点**的情形，注意到此时$$c$$也一定是**割点**
（如果$$c$$是叶子结点，这种情形还未讨论，因为此时$$sz(c), \overline{sz}(c)$$有一个是$$0$$）

于是，我们接下来要讨论$$c$$是方点，$$c$$是叶子结点的两种情形
![](/media/content_img/block-tree.png)
方点$$x$$也像圆点一样处理，只不过此时我们不能把方点选作$$c$$，而是要从`deg(x)`这些点中任选一个作为$$c$$
那么，哪些点不能选呢？

和圆点统计一样，我们找两个分支$$\\{ sz, \overline{sz} \\}$$，假设从这两个分支中选出了$$u, v$$
那么$$u \to x, v \to x$$的**简单路径**，一定会经过$$u', v'$$，其中$$u', v'$$和$$x$$相邻，且是圆点也是割点
$$c$$不能取这两个点（这就是之前讨论的第一种情况），剩下的点都可以取
当然这里$$c$$也包含了叶子结点的情况

综上所述，$$c$$能取的值有$$\text{deg}(x) - 2$$种，综上所述，假设当前考虑方点$$x$$
此时$$tot = sz(x) + \overline{sz}(x)$$（此时不需要`-1`，因为方点是虚拟的点）
对$$x$$的每个儿子$$y$$，$$ans += (deg(x)-2) \cdot sz(y) \cdot (tot - sz(y))$$
若考虑根节点往上的分支，$$ans += (deg(x)-2) \cdot up(y) \cdot (tot - up(y))$$（这里$$up$$就是$$\overline{sz}$$）

####  APIO 2018 实现
```bash
typedef pair<int, int> PII;
const int maxn = 1e5 + 10;
vector<vector<int> > G(maxn, vector<int>()), tr(maxn<<1, vector<int>());
vector<int> dfn(maxn, 0), low(maxn, 0);
vector<int> cut(maxn, 0), sz(maxn<<1, 0), up(maxn<<1, 0);

void solve(int n, int tot) {
    function<void(int, int)> dfs = [&](int u, int fa) -> void {
        sz[u] += (u <= n);
        for (auto v : tr[u]) if (v != fa) {
            dfs(v, u);
            sz[u] += sz[v];
        }
    };
    for (int i = 1; i <= tot; i++) if (!sz[i]) dfs(i, 0);

ll ans = 0;
    function<void(int, int)> dfs2 = [&](int u, int fa) -> void {
        if (fa != 0) up[u] = up[fa] + (sz[fa] - sz[u]);
        for (auto v : tr[u]) if (v != fa) dfs2(v, u);

if (u <= n) {
            ll sum = (ll)sz[u]+up[u]-1;
            
            ans += 1LL*up[u] * (sum-up[u]);
            for (auto v : tr[u]) {
                if (v == fa) continue;
                ans += 1LL*sz[v] * (sum-sz[v]);
            }
        }
        else {
            ll sum = (ll)sz[u]+up[u];

ans += (1LL*tr[u].size() - 2) * up[u] * (sum-up[u]);
            for (auto v : tr[u]) {
                if (v == fa) continue;
                ans += (1LL*tr[u].size() - 2) * sz[v] * (sum-sz[v]);
            }
        }
    };

for (int i = 1; i <= tot; i++) if (!up[i]) dfs2(i, 0);
    printf("%lld\n", ans);
}

int main() {
    freopen("input.txt", "r", stdin);
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }

int idx = 0, tot = n;
    stack<int> stk;
    function<void(int, int, int)> dfs = [&](int u, int fa, const int root) -> void {
        dfn[u] = low[u] = ++idx;
        stk.push(u);

int ch = 0;
        for (auto v : G[u]) {
            if (!dfn[v]) {
                dfs(v, u, root);
                ch += 1;
                low[u] = min(low[u], low[v]);

if (low[v] >= dfn[u]) {
                    ++tot;
                    cut[u] = 1;

while (true) {
                        auto x = stk.top();
                        stk.pop();
                        tr[tot].push_back(x), tr[x].push_back(tot);
                        if (x == v) break;
                    }
                    tr[tot].push_back(u), tr[u].push_back(tot);
                }
            }
            else if (v != fa) low[u] = min(low[u], dfn[v]);
        }

if (u == root && ch <= 1) cut[u] = 0;
    };
    
    for (int i = 1; i <= n; i++) if (!dfn[i]) {
        dfs(i, 0, i);
        while (stk.size()) stk.pop();
    }

// block tree tr[1...tot]
    solve(n, tot);
}
```

上一篇：图的连通性，有向图强连通分量下一篇：双连通分量的一些例子

看完文章有啥想法