【学习笔记】无向图的连通性

# 割点

**定义：** 在无向图连通图中，若把点 $x$ 删去后整个图就不连通了，则 $x$ 为割点（割顶）。

**朴素方法：** 每次删去一个点，然后判断图是否连通，时间复杂度为 $O(n(n+m))$。

**Tarjan 算法：**

$dfn_x$：$x$ 被 `dfs` 到的时间戳

$low_x$：在 $x$ 及以后被搜索的所有节点的 $low$ 值和这些节点能到达的节点的 $dfn$ 的最小值。

**算法流程：**

1. 从 $1$ 号点开始遍历全图，对于遍历到的点 $x$，记录它的 $dfn_x$ 并将 $low_x$ 的值赋为 $dfn_x$。
2. 接下来遍历 $x$ 的所有子儿子 $y$：
- 若 $y$ 被访问过，则 $low_x=\min(low_x,dfn_y)$。
- 若 $y$ 没有被访问过，则先遍历 $y$，接着 $low_x=\min(low_x,low_y)$。

**算法原理：**

若点 $x$ 不为割点，把所有没被访问过 $y$ 放在 $x$ 的“下方”，则必存在一条边从 $y$ 连到 $x$ 的“上方”且这条边在 $x$ 的“右边”（不然应该先访问到这条边，或者说访问顺序在 $x$ 之后），按照 $low$ 数组的定义，则所以的 $y$ 都满足 $low_y<dfn_x$。

相反，若 $x$ 为割点，则必有 $low_y\ge dfn_x$（注意，这里有等于号，因为若连到自己则仍为割点）。

**特例：** 若 $x$ 为根节点，则肯定存在 $low_y\ge dfn_x$，判断不出割点，需要特判一下：如果 $x$ 连接的联通块个数 $\ge 2$，则其断开后这几个联通块会分开，则 $x$ 为割点。

```cpp
void tarjan(int k, int rt) {
int cnt = 0;
dfn[k] = low[k] = ++s;
for (auto i : p[k]) {
if (!dfn[i]) {
cnt++;
tarjan(i, rt);
low[k] = min(low[k], low[i]);
if (k != rt && low[i] >= dfn[k]) {
if (!flag[k]) ans++;
flag[k] = true;
}
}
else low[k] = min(low[k], dfn[i]);
}
if (k == rt && cnt > 1) {
if (!flag[k]) ans++;
flag[k] = true;
}
}
```
**时间复杂度：**$O(n+m)$

# 割边
**定义：** 在无向连通图中，若删去某条边，这个图就不连通了，则称这条边是割边（桥）。

**Tarjan 算法：**

求割边的算法与求割点的算法差不多，只是如果一条从 $x$ 到 $y$ 的边为割边，则 $y$ 不存在边能到 $y$ 节点及其“上方”，即存在 $y$ 使 $low_y>dfn_x$（这里和割点有所区别）。

代码实现时要注意，这里的边是双向边，为了每条边只访问一次，可以使用邻接链表来存图，这样在边表中一条边 $e$ 的反向边为 $e\oplus1$，注意这样存图边的编号得从 $2$ 开始。

```cpp
void tarjan(int k) {
int cnt = 0;
dfn[k] = low[k] = ++s;
for (int i = head[k]; i; i = e[i].nxt) {
if (vis[i]) continue;
vis[i] = vis[i ^ 1] = true;
if (!dfn[e[i].to]) {
tarjan(e[i].to);
low[k] = min(low[k], low[e[i].to]);
if (low[e[i].to] > dfn[k])
bri[i] = bri[i ^ 1] = true;
}
else low[k] = min(low[k], dfn[e[i].to]);
}
}
```

**时间复杂度：**$O(n+m)$

# 点双连通分量（v-Dcc）
**定义：** 无向图中极大的（不能往外扩张）不存在割点的连通图（割点是指“局部”的割点），其任意两点之间都存在不经过重复点的两条路径。

**性质：** 一个割点可以存在于多个点双连通分量中，非割点只能存在于一个点双连通分量中，否则其就不是“分量”。

**求法：** 同样是 Tarjan 算法，不过要开一个栈记录：遍历到 $x$ 时便把 $x$ 压入栈，若 $x$ 为割点，则它通过当前点“吊”着的所有点都弹出（$x$ 不弹出），而 $x$ 则是由“吊”着它的点弹出。有个注意点，到 $y$ 时只应弹出 $y$ 吊着的这一串，而不是把 $x$ 吊的所有点都弹出。

**特例：** 当 $x$ 为孤立点时，它自成一个点双连通分量。

```cpp
void tarjan(int k) {
q.push(k);
dfn[k] = low[k] = ++s;
int sum = 0;
for (auto i : p[k]) {
if (!dfn[i]) {
sum++;
tarjan(i);
low[k] = min(low[k], low[i]);
if (low[i] >= dfn[k]) {
cnt++;
int t;
do {
t = q.top();
ans[cnt].push_back(q.top());
q.pop();
}while (t != i);
ans[cnt].push_back(k);
}
}
else low[k] = min(low[k], dfn[i]);
}
if (k == rt && sum == 0) ans[++cnt].push_back(k);
}
```
**时间复杂度：**$O(n+m)$
# 边双连通分量
**定义：** 无向图中极大的（不能往外扩张）不存在割边的连通图，其任意两点之间都存在不经过重复边的两条路径。

**性质：** 割边可以不存在于任何边双连通分量中，非割边只能存在于一个边双连通分量中。

**求法：** 由于边双连通分量中不包含割边，那么就可以先跑一遍 Tarjan 标记出割边，然后 dfs，不经过割边跑出的联通块就是边双连通分量。

```cpp
//省略 Tarjan 函数
void dfs(int k)
{
ans[sum].push_back(k);
vis[k] = true;
for (int i = head[k]; i; i = e[i].nxt)
{
if (bri[i]) continue;
int v = e[i].to;
if (!vis[v]) dfs(v);
}
}
```

# 练习题

[ $\color{#9D3DCF}\texttt{SP2878 KNIGHTS - Knights of the Round Table}$](https://www.luogu.com.cn/problem/SP2878)

[ $\color{#3498DB}\texttt{P3469 [POI2008] BLO-Blockade}$](https://www.luogu.com.cn/problem/P3469)

[ $\color{#3498DB}\texttt{P2860 [USACO06JAN] Redundant Paths G}$](https://www.luogu.com.cn/problem/P2860)