连通性相关
# 连通性相关
# 强连通分量
有向图 强连通是指, 中任意两个结点连通
强连通分量(Strongly Connected Components,SCC)的定义是:极大的强连通子图
在介绍 Tarjan 算法之前,需要了解 DFS 生成树
# DFS 生成树
有向图的 DFS 生成树主要有 4 种边(不一定全部出现):
- 树边(tree edge):示意图中以黑色边表示,每次搜索找到一个还没有访问过的结点的时候就形成了一条树边
- 反祖边(back edge):示意图中以红色边表示(即 ),也被叫做回边,即指向祖先结点的边
- 横叉边(cross edge):示意图中以蓝色边表示(即 ),它主要是在搜索的时候遇到了一个已经访问过的结点,但是这个结点 并不是 当前结点的祖先
- 前向边(forward edge):示意图中以绿色边表示(即 ),它是在搜索的时候遇到子树中的结点的时候形成的
我们考虑 DFS 生成树与强连通分量之间的关系
如果结点 是某个强连通分量在搜索树中遇到的第一个结点,那么这个强连通分量的其余结点肯定是在搜索树中以 为根的子树中。结点 被称为这个强连通分量的根
# Tarjan 算法
在 Tarjan 算法中为每个结点 维护了以下几个变量:
- :深度优先搜索遍历时结点 u 被搜索的次序
- :在 的子树中能够回溯到的最早的已经在栈中的结点。设以 为根的子树为 。 定义为以下结点的 的最小值: 中的结点;从 通过一条不在搜索树上的边能到达的结点
一个结点的子树内结点的 dfn 都大于该结点的 dfn
从根开始的一条路径上的 dfn 严格递增,low 严格非降
按照深度优先搜索算法搜索的次序对图中所有的结点进行搜索,维护每个结点的 与 变量,且让搜索到的结点入栈。
在搜索过程中,对于结点 u 和与其相邻的结点 v(v 不是 u 的父节点)考虑 3 种情况:
- 未被访问(树边):继续对 进行深度搜索。在回溯过程中,用 更新 。因为存在从 到 的直接路径,所以 能够回溯到的已经在栈中的结点, 也一定能够回溯到
- 被访问过,已经在栈中(反祖边):根据 的定义,用 更新
- 被访问过,且不在栈中(横叉边/前向边):说明 已经搜索完毕,所以不对其做处理
对于一个连通分量,很容易想到,在该连通图中,有且仅有一个 。该结点一定是在深度遍历的过程中,该连通分量中第一个被访问过的结点,因为它的 和 值最小,不会被该连通分量中的其他结点所影响
因此,在回溯的过程中,判定 是否成立,如果成立,则栈中 u 及其上方的结点构成一个 SCC
struct Tarjan {
int n; // index from 1
vector<int> dfn, low, scc, in_stk;
stack<int> stk;
int cnt, scc_cnt;
Tarjan(int n_) {
n = n_;
dfn.resize(n + 1); low.resize(n + 1); scc.resize(n + 1); in_stk.resize(n + 1);
cnt = 0; scc_cnt = 0;
while (!stk.empty()) stk.pop();
fill(in_stk.begin(), in_stk.end(), 0);
}
void tarjan(int u) {
low[u] = dfn[u] = ++cnt; stk.push(u); in_stk[u] = 1;
for (int v : g[u]) {
if (!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
}
else if (in_stk[v]) low[u] = min(low[u], dfn[v]);
}
if (low[u] == dfn[u]) { // 从栈顶到u为一个强连通分量
scc_cnt++;
while (true) {
int x = stk.top(); stk.pop(); in_stk[x] = 0;
scc[x] = scc_cnt;
if (x == u) break;
}
}
}
};
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
# 割点
对于一个无向图,如果把一个点删除后这个图的极大连通分量数增加了,那么这个点就是这个图的割点(又称割顶)
图中,很容易看出割点的个数为 ,是 结点
首先,我们按照 DFS 序给他打上时间戳(访问的顺序),记在 数组中
然后需要构造一个 数组,用它来存储 不经过其父亲能到达的最小的时间戳,和 Tarjan 求强连通分量的定义一样
例如 的话是 , 和 是
那么,判断一个结点 是不是割点:只需要存在一个儿子 ,满足 ,可以这样理解,就是往这个儿子这边走就不可能 "逃" 到 的上面了,说明只要删除了 , 的上面部分和这个儿子 必然不连通
这个结论对根结点是不适用的,需要特殊处理,如果在生成树中,根结点只有一个儿子,那么就不是割点,否则就是割点
struct Tarjan {
int n;
vector<int> low, dfn, cut;
int cnt;
Tarjan(int n_) {
n = n_; // index = 1
low.resize(n + 1); dfn.resize(n + 1); cut.clear();
cnt = 0;
}
void tarjan(int u, bool is_root = 1) {
int sum = 0;
low[u] = dfn[u] = ++cnt;
for (int v : g[u]) {
if (!dfn[v]) {
tarjan(v, 0);
low[u] = min(low[u], low[v]);
if (low[v] >= dfn[u]) sum += 1;
}
else
low[u] = min(low[u], dfn[v]);
}
if (sum >= 2 || (is_root && sum >= 1)) cut.push_back(u); // 如果是根节点,需要判断是否有两个子树
}
};
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
# 割边
对于一个无向图,如果删掉一条边后图中的连通分量数增加了,则称这条边为桥或者割边。
比如说,下图中
红色的边就是割边
和割点差不多,只要改一处: 就可以了,而且不需要考虑根节点的问题。
对于一个结点 的儿子结点 ,如果满足 ,说明无法从 走到 的父节点或者返回 ,所以 这条边就是一条割边
struct Tarjan {
int n; // index from 1
vector<int> low, dfn;
vector<pair<int, int>> bridge;
int cnt;
Tarjan(int n_) {
n = n_;
low.resize(n + 1); dfn.resize(n + 1);
cnt = 0; bridge.clear();
}
void tarjan(int u, int fa = -1) {
dfn[u] = low[u] = ++cnt;
for (int v : g[u]) {
if (v == fa) continue;
if (!dfn[v]) {
tarjan(v, u);
low[u] = min(low[u], low[v]);
if (low[v] > dfn[u]) bridge.push_back({u, v});
} else {
low[u] = min(low[u], dfn[v]);
}
}
}
};
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