连通性相关算法

有向图的强连通分量

强连通的定义是：有向图 G 强连通是指，G 中任意两个结点连通。

强连通分量（Strongly Connected Components，SCC）的定义是：极大的强连通子图。

这里要介绍的是如何来求强连通分量。

DFS 生成树

在介绍该算法之前，先来了解 DFS 生成树，我们以下面的有向图为例：

DFS 生成树

有向图的 DFS 生成树主要有 4 种边（不一定全部出现）：

树边（tree edge）：示意图中以黑色边表示，每次搜索找到一个还没有访问过的结点的时候就形成了一条树边。
反祖边（back edge）：示意图中以红色边表示（即 $7 \rightarrow 1$），也被叫做回边，即指向祖先结点的边。
横叉边（cross edge）：示意图中以蓝色边表示（即 $9 \rightarrow 7$），它主要是在搜索的时候遇到了一个已经访问过的结点，但是这个结点 并不是 当前结点的祖先。
前向边（forward edge）：示意图中以绿色边表示（即 $3 \rightarrow 6$），它是在搜索的时候遇到子树中的结点的时候形成的。

我们考虑 DFS 生成树与强连通分量之间的关系。

如果结点 $u$ 是某个强连通分量在搜索树中遇到的第一个结点，那么这个强连通分量的其余结点肯定是在搜索树中以 $u$ 为根的子树中。结点 $u$ 被称为这个强连通分量的根。

反证法：假设有个结点 $v$ 在该强连通分量中但是不在以 $u$ 为根的子树中，那么 $u$ 到 $v$ 的路径中肯定有一条离开子树的边。但是这样的边只可能是横叉边或者反祖边，然而这两条边都要求指向的结点已经被访问过了，这就和 $u$ 是第一个访问的结点矛盾了。得证。

tarjan算法求强连通分量

在 Tarjan 算法中为每个结点 $u$ 维护了以下几个变量：

$\textit{dfn}_u$：深度优先搜索遍历时结点 $u$ 被搜索的次序。
$\textit{low}_u$：在 $u$ 的子树中能够回溯到的最早的已经在栈中的结点。设以 $u$ 为根的子树为 $\textit{Subtree}_u$。$\textit{low}_u$ 定义为以下结点的 $\textit{dfn}$ 的最小值：$\textit{Subtree}_u$ 中的结点；从 $\textit{Subtree}_u$ 通过一条不在搜索树上的边能到达的结点。

一个结点的子树内结点的 dfn 都大于该结点的 dfn。

从根开始的一条路径上的 dfn 严格递增，low 严格非降。

按照深度优先搜索算法搜索的次序对图中所有的结点进行搜索，维护每个结点的 dfn 与 low 变量，且让搜索到的结点入栈。每当找到一个强连通元素，就按照该元素包含结点数目让栈中元素出栈。在搜索过程中，对于结点 $u$ 和与其相邻的结点 $v$（$v$ 不是 $u$ 的父节点）考虑 3 种情况：

$v$ 未被访问：继续对 $v$ 进行深度搜索。在回溯过程中，用 $\textit{low}_v$ 更新 $\textit{low}_u$。因为存在从 $u$ 到 $v$ 的直接路径，所以 $v$ 能够回溯到的已经在栈中的结点，$u$ 也一定能够回溯到。
$v$ 被访问过，已经在栈中：根据 low 值的定义，用 $\textit{dfn}_v$ 更新 $\textit{low}_u$。
$v$ 被访问过，已不在栈中：说明 $v$ 已搜索完毕，其所在连通分量已被处理，所以不用对其做操作。

代码模板

void tarjan(int u) {
    dfn[u] = low[u] = ++timestamp;
    stk.push(u), in_stk[u] = true;
    for (auto v: g[u]) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (in_stk[v]) { // v在栈里，说明是后向边
            low[u] = min(low[u], dfn[v]);
        }
    }
    
    if (low[u] == dfn[u]) {
        scc_cnt ++;
        int y;
        do {
            y = stk.top();
            stk.pop();
            id[y] = scc_cnt;
            scc_size[scc_cnt] ++;
        } while (y != u);
    }
}

习题

无向图的双连通分量

割点和桥的定义

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

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

边双连通具有传递性，即，若 $x,y$ 边双连通，$y,z$ 边双连通，则 $x,z$ 边双连通。

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

bcc-0

割点

对于一个无向图，如果把一个点删除后这个图的极大连通分量数增加了，那么这个点就是这个图的割点（又称割顶）。

比如说，下面图中，点2就是割点

割边

和割点差不多，叫做桥。

对于一个无向图，如果删掉一条边后图中的连通分量数增加了，则称这条边为桥或者割边。严谨来说，就是：假设有连通图 $G={V,E}$，$e$ 是其中一条边（即 $e \in E$），如果 $G-e$ 是不连通的，则边 $e$ 是图 $G$ 的一条割边（桥）。

比如说，下图中，

割边示例图

红色的边就是割边。

DFS 找桥并判断边双连通

首先，对原图进行 DFS。

如上图所示，黑色与绿色边为树边，红色边为非树边（可能为返祖边和横叉边）。每一条非树边连接的两个点都对应了树上的一条简单路径，我们说这条非树边覆盖了这条树上路径上所有的边。绿色的树边至少被一条非树边覆盖，黑色的树边不被任何非树边覆盖。

我们如何判断一条边是不是桥呢？显然，非树边和绿色的树边一定不是桥，黑色的树边一定是桥。

不难发现，对于红色边所在的环，其中的点的low值都小于等于环上最高的点，因为他们都能通过红色边回到环上的最高点。

而对于图中黑色的边，其父节点的dfn值一定小于子节点的low值，反证法：记当前边的编号为a，父亲节点的编号为f，子节点的编号为s，如果子节点的low值小于等于父亲节点的dfn值，那么从子节点出发，一定有一条不经过边a的简单路径，使得除了a以外，还有一条简单路径连接能够连接f和s，根据定义，边a不是桥。

所以，只需要在dfs的时候判断一下dfn[u] < low[j]即可确定一个桥

用以上的方法 $O(n+m)$ 求出每条边分别是否是桥后，两个点是边双连通的，当且仅当它们的树上路径中不包含桥。

tarjan算法求桥模板

int n, m, timestamp, dcc_cnt;
int dfn[N], low[N];
int h[N], e[M], ne[M], idx;
stack<int> stk;
bool is_bridge[M];
int d[N], id[N];

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void tarjan(int u, int from) { // u 是当前节点，from是来的边的id
    dfn[u] = low[u] = ++ timestamp;
    stk[++ top] = u;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (!dfn[j]) {
            tarjan(j, i);
            low[u] = min(low[u], low[j]);
            if (dfn[u] < low[j]) {
                is_brige[i] = is_brige[i ^ 1] = true;   // i ^ 1 是另一条边， 标记一正一反两条边为桥
            }
        } else if (i != (from ^ 1)) {
            low[u] = min(low[u], dfn[j]);
        }
    }

    if (low[u] == dfn[u]) {
        int y;
        dcc_cnt ++;
        do {
            y = stk[top --];
            id[y] = dcc_cnt;
        } while (y != u);
    }
}

DFS 找割点并判断点双连通

如果我们尝试删除每个点，并且判断这个图的连通性，那么复杂度会特别的高。所以要介绍一个常用的算法：Tarjan。

首先，我们上一个图：

很容易的看出割点是 2，而且这个图仅有这一个割点。

首先，我们按照 DFS 序给他打上时间戳（访问的顺序）。

这些信息被我们保存在一个叫做 dfn 的数组中。

还需要另外一个数组 low，用它来存储不经过其父亲能到达的最小的时间戳。

例如 low[2] 的话是 1，low[5] 和 low[6] 是 3。

然后我们开始 DFS，我们判断某个点是否是割点的根据是：对于某个顶点 $u$，如果存在至少一个顶点 $v$（$u$ 的儿子），使得 $low_v \geq dfn_u$，即不能回到祖先，那么 $u$ 点为割点。

此根据惟独不适用于搜索的起始点，其需要特殊考虑：若该点不是割点，则其他路径亦能到达全部结点，因此从起始点只「向下搜了一次」，即在搜索树内仅有一个子结点。如果在搜索树内有两个及以上的儿子，那么他一定是割点了（设想上图从 2 开始搜索，搜索树内应有两个子结点：3 或 4 及 5 或 6）。如果只有一个儿子，那么把它删掉，不会有任何的影响。比如下面这个图，此处形成了一个环。

我们在访问 1 的儿子时候，假设先 DFS 到了 2，然后标记用过，然后递归往下，来到了 4，4 又来到了 3，当递归回溯的时候，会发现 3 已经被访问过了，所以不是割点。

更新 low 的伪代码如下：

1
2
3

如果 v 是 u 的儿子 low[u] = min(low[u], low[v]);
否则
low[u] = min(low[u], dfn[v]);

总结性的说，我们在执行tarjan算法的时候，对于一条边{x, y}，当low[y] >= dfn[x]时

如果x不是根节点，那么x是割点
如果x是根节点，当至少存在两个子节点y，有low[y] >= dfn[x]时，x是割点，否则不是割点

tarjan找割点模板

void tarjan(int u) {
    dfn[u] = low[u] = ++ timestamp;
    stk[++ top] = u;

    if (u == root && h[u] == -1) {
        dcc_cnt ++;
        dcc[dcc_cnt].push_back(u);
        return;
    }

    int cnt = 0;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (!dfn[j]) {
            tarjan(j);
            low[u] = min(low[u], low[j]);
            if (dfn[u] <= low[j]) {
                cnt ++;
                if (u != root || cnt > 1) cut[u] = true;
                dcc_cnt ++;
                int y;
                do {
                    y = stk[top --];
                    dcc[dcc_cnt].push_back(y);
                } while (y != j);
                dcc[dcc_cnt].push_back(u);
            }
        }
        else low[u] = min(low[u], dfn[j]);
    }
}

点双连通分量缩点

每个割点单独作为一个点
从每个v-dcc向其他所包含的每个割点连边

习题

求解桥的数目：3177 – Redundant Paths (poj.org)
求解割点的数目：#10103. 「一本通 3.6 练习 4」电力 - 题目 - LibreOJ (loj.ac)
[P3225 HNOI2012] 矿场搭建 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

一些有用的结论

把一个图变成强连通：需要加边数量为：max{q,p}，其中p,q分别为缩点后，入度为0的的点数量和出度为0的点数量

把一个图变成双联通：需要加边数量为：$\lfloor (cnt + 1) / 2 \rfloor$，其中cnt为缩点后叶子节点的数量

#tarjan #割点和桥 #强连通 #双连通

连通性相关算法

https://www.lry666.cn/posts/9ce6/

作者

LRY666

发布于

2024年4月6日

许可协议

连通性相关问题题解上一篇

win11系统下使用iedriver开发带有activex控件的网站的自动化脚本下一篇