连通性相关算法

有向图的强连通分量

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

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

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

DFS 生成树

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

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

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

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

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

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

tarjan算法求强连通分量

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

  1. ：深度优先搜索遍历时结点 被搜索的次序。
  2. ：在 的子树中能够回溯到的最早的已经在栈中的结点。设以 为根的子树为 。 定义为以下结点的 的最小值： 中的结点；从 通过一条不在搜索树上的边能到达的结点。

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

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

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

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

代码模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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);
    }
}
CPP

习题

无向图的双连通分量

割点和桥的定义

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

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

边双连通具有传递性，即，若 边双连通， 边双连通，则 边双连通。

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

割点

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

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

割边

和割点差不多，叫做桥。

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

比如说，下图中，

红色的边就是割边。

DFS 找桥并判断边双连通

首先，对原图进行 DFS。

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

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

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

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

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

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

tarjan算法求桥模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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);
    }
}
CPP

DFS 找割点并判断点双连通

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

首先，我们上一个图：

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

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

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

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

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

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

此根据惟独不适用于搜索的起始点，其需要特殊考虑：若该点不是割点，则其他路径亦能到达全部结点，因此从起始点只「向下搜了一次」，即在搜索树内仅有一个子结点。如果在搜索树内有两个及以上的儿子，那么他一定是割点了（设想上图从 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]);
CPP

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

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

tarjan找割点模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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]);
    }
}
CPP

点双连通分量缩点

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

习题

一些有用的结论

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

把一个图变成双联通：需要加边数量为：，其中cnt为缩点后叶子节点的数量