图论基础

无向图的连通性

一些定义

在无向连通图 $G$ 上进行如下定义:

割点:若删掉某点 $P$ 后,$G$ 分裂成两个或两个以上的子图,则称 $P$ 为 $G$ 的割点。

割点集合:如果有一个顶点集合,删除这个顶点集合以及与该点集中的顶点相关联的边以后,原图分成多于一个连通块,则称这个点集为 $G$ 的割点集合。

点连通度:最小割点集合的大小称为无向图 $G$ 的点连通度。

割边(桥):若删掉某条边 $e$ 后,$G$ 分裂成两个或两个以上的子图,则称 $e$ 为 $G$ 的割边(桥)。

割边集合:如果有一个边集合,删除这个边集后,原图分成多于一个连通块,则称这个边集为割边集合。

边连通度:最小割边集合的大小称为无向图 $G$ 的边连通度。

点双连通图:点连通度大于 $1$ 的图称为点双连通图(没有割点)。

边双连通图:边连通度大于 $1$ 的图称为边双连通图(没有割边)。

(点/边)双连通分量:无向图的极大(点/边)双连通子图称为(点/边)双连通分量。


Tarjan 算法

Tarjan 基于对图的深度优先搜索,对每个节点引入了两个值:

$dfn[u]$:节点 $u$ 的时间戳,记录点 $u$ 是 $DFS$ 过程中第几个访问的节点。

$low[u]:$ 记录节点 $u$ 或 $u$ 的子树 不经过搜索树上的边能够到达的时间戳最小的节点。

维护方法

对于每一条与 $u$ 相连的边 $(u,v)$

若在搜索树上 $v$ 是 $u$ 的子节点,则更新 $low[u] = min ( low[u], low[v] )$

若 $(u,v)$ 不是搜索树上的边,则更新 $low[u] = min(low[u], dfn[v])$

求割点

对于搜索树上的一条边 $(u,v)$,其中 $u$ 是 $v$ 的父节点,若 $low[v] >= dfn[u]$,则 $u$ 为割点。

$low[v] >= dfn[u]$ 说明从 $v$ 及 $v$ 的子树的点 到以 $u$ 为根的子树之外的点必须要经过点 $u$,因此 $u$ 是割点。

注意: 如果根只有一个孩子,那么它不是割点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<int> G[maxn];
int dfs_clock, dfn[maxn];
bool iscut[maxn];
int dfs(int u, int fa) {
int lowu = dfn[u] = ++dfs_clock;
int child = 0;
for (auto &v : G[u]) {
if (!dfn[v]) {
child++;
int lowv = dfs(v, u);
lowu = min(lowu, lowv);
if (lowv >= dfn[u]) iscut[u] = true;
} else if (dfn[v] < dfn[u] && v != fa)
lowu = min(lowu, dfn[v]);
}
if (fa < 0 && child == 1) iscut[u] = false; // root
return lowu;
}

点双联通分量

其他定义:对于一个无向连通图,如果任意两点至少存在两条点不重复路径,则称这个图为点双连通的。

可以在求割点的过程中维护一个栈,从而求出每个点双连通分量。

建立一个栈,存储 DFS 过程中访问的节点, 初次访问一个点时把该点入栈。

如果边 $(u,v)$ 满足 $low[v] >= dfn[u]$,即满足了 $u$ 是割点的判断条件,那么把点从栈顶依次取出,直至取出了点 $v$,取出的这些点和点 $u$ 一起组成了一个点双连通分量。

割点可能属于多个点双连通分量,其余点和每条边属于且仅属于一个点双连通分量。因此在从栈中取出节点时,要把 $u$ 留在占中。

整个 $DFS$ 结束后,栈中还剩余的节点构成一个点双联通分量。

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
37
38
39
40
41
42
43
44
45
46
47
vector<int> G[maxn], bcc[maxn];
int bcc_cnt, dfs_clock;
int dfn[maxn], iscut[maxn], bccno[maxn];
stack<pii> stk;
int dfs(int u) {
int lowu = dfn[u] = ++dfs_clock;
int child = 0;
for (auto &v : G[u]) {
pii e = {u, v};
if (!dfn[v]) {
stk.push(e);
child++;
int lowv = dfs(v, u);
lowu = min(lowu, lowv);
if (lowv >= dfn[u]) { // u为割点
iscut[u] = true;
bcc_cnt++;
bcc[bcc_cnt].clear(); //注意!bcc从1开始编号
for (;;) {
pii x = stk.top();
stk.pop();
if (bccno[x.first] != bcc_cnt)
bcc[bcc_cnt].push_back(x.first), bcc[x.first] = bcc_cnt;
if (bccno[x.second] != bcc_cnt)
bcc[bcc_cnt].push_back(x.second),
bcc[x.second] = bcc_cnt;
if (x.first == u && x.second == v) break;
}
}
} else if (dfn[v] < dfn[u] && v != fa) {
stk.push(e);
lowu = min(lowu, dfn[v]);
}
}
if (fa < 0 && child == 1) iscut[u] = 0;
return lowu;
}
//割点的bccno无意义
void solve(int n) {
//调用结束后stack保证为空,所以不用清空
memset(iscut, 0, sizeof(iscut));
memset(bccno, 0, sizeof(bccno));
memset(dfn, 0, sizeof(dfn));
dfs_clock = bcc_cnt = 0;
for (int i = 0; i < n; i++)
if (!dfn[i]) dfs(i, -1);
}

注意对每个割点或者割边来说,判定定理可能不止一次成立,所以不要边判定边输出。

割边

对于一条搜索树上的边 $(u,v)$,其中 $u$ 是 $v$ 的父节点,若 $low[v] > dfn[u]$,则 $(u,v)$ 是桥。

$low[v]$ 表示 $v$ 和 $v$ 的子树不经过搜索树上的边能够到达的时间戳的最小的节点。

$low[v] > dfn[u]$ 说明从以 $v$ 为根的子树到子树之外的必须要经过边 $(u,v)$,因此 $(u,v)$ 是桥。

可以像求割点一样,当 $v$ 回溯至 $u$ 后,判断上述不等式是否成立。

另一种判断方法:当递归 $v$ 结束时,如果 $low[v] == dfn[v]$ 说明 $v$ 和 $v$ 的父节点之间的边是桥。

注意:在有重边的图上求桥,需要对重边加以区分。需要记录 $(u,fa)$ 的数量,若大于 $1$ 说明有重边,则要设置 $low[u] = dfn[fa]$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<pii> G[maxn];  // first: 下一个点, second: 该边的编号
int dfs_clock, dfn[maxn];
bool iscut[N]; // N: 边数

int dfs(int u, int fa) {
int lowu = dfn[u] = ++dfs_clock;
// int father = 0;
for (auto &V : G[u]) {
int v = V.first;
int id = V.second; // 边的编号
// if(v == fa) father++;
if (!dfn[v]) {
int lowv = dfs(v, u);
lowu = min(lowv, lowu);
if (lowv > dfn[u]) iscut[id] = true;
} else if (dfn[v] < dfn[u] && v != fa)
lowu = min(lowu, dfn[v]);
}
// if(father > 1) return dfn[fa];
return lowu;
}

边双联通分量

其他定义:对于一个无向连通图,如果任意两点至少存在两条边不重复路径,则称该图为边双连通的。

边双连通分量的求法非常简单,只需在求出所有的桥后,把桥删除。

此时原图分成了若干个连通块,每个连通块就是一个边双连通分量。

桥不属于任何一个边双连通分量

其余的边和每个顶点都属于且仅属于一个边双连通分量。

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
vector<int> G[maxn];
int bcc_cnt, dfs_clock;
int dfn[maxn], bccno[maxn];
stack<int> stk;
int dfs(int u, int fa) {
int lowu = dfn[u] = ++dfs_clock;
stk.push(u);
bool flag = false; // 有重边
for (auto &v : G[u]) {
if (v == fa && !flag) {
flag = true;
continue;
}
if (!dfn[v]) {
int lowv = dfs(v, u);
lowu = min(lowu, lowv);
} else
lowu = min(lowu, dfn[v]);
}
if (lowu == dfn[u]) {
bcc_cnt++; // 编号从1开始
while (!stk.empty()) {
int v = stk.top();
bccno[v] = bcc_cnt;
if (u == v) break;
}
}
}

边双连通分量的构造

任意给定一个无向连通图,最少添加多少条边可以把它变为双连通图?

求出所有的桥和边双连通分量,把每个双连通分量缩成一个点。

此时的图只包含缩点后的双连通分量 和 桥边,是一棵无根树。

统计树中度数为 $1$ 的节点的个数 $cnt$ 。把树变为边双连通图,至少需要添加 $\lceil \frac{cnt}{2} \rceil$ 条边。

构造方法

设缩点后的叶子为 $v_1, v_2, … , v_n$,让 $v_i$ 与 $v_{i + \lfloor \frac{n}{2} \rfloor}$ 连边即可。

如果相连的两个节点的 $LCA$ 不是根的话,必然会留下一些桥(根到 $LCA$ 的路径上都是桥)。

有向图连通性

强连通分量

若在一张有向图中,各个点互相可达,则称此图强连通。

最大强连通子图又称强连通分量。

实际问题中,强连通分量往往会被看成一个点来处理(缩点)。

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
37
38
39
40
41
42
vector<int> G[maxn];
int scc, dfs_clock, top; // scc: 强连通分量的数量
bool instack[maxn];
int dfn[maxn], low[maxn], belong[maxn], Stack[maxn];
// int num[maxn]; // 每个强连通分量的数量。 1 ~ scc
// int maps[maxn]; //缩点之后 每个点对应的新点的标号
void Tarjan(int u) {
dfn[u] = low[u] = ++dfs_clock;
instack[u] = true;
Stack[top++] = u;
for (auto &v : G[u]) {
if (!dfn[v]) {
Tarjan(v);
low[u] = min(low[u], low[v]);
} else if (instack[v])
low[u] = min(low[u], dfn[v]);
}
if (dfn[u] == low[u]) {
++scc;
int cnt = 0;
int now;
while (top > 0) {
now = Stack[--top];
instack[now] = false;
belong[now] = u;
++cnt;
if (now == u) {
// num[scc] = cnt;
// maps[u] = scc;
break;
}
}
}
}
void solve(int n) {
memset(instack, 0, sizeof(instack));
memset(dfn, 0, sizeof(dfn));
scc = dfs_clock = top = 0;
for (int i = 1; i <= n; i++) { // 点的标号从1开始
if (!dfn[i]) Tarjan(i);
}
}

有向图的必经结点(割点)(支配树)

给定有向图 $G$(可能有环)和图中的一个点 $s$,对于 $G$ 中的任意一个点 $t$,求从 $s$ 到 $t$ 的路径上(可能有很多条)必须经过的点集。

支配树:$(G,s)$ 的支配树是一棵根为 $s$ 的有向树,从 $s$ 出发可以到达 $G$ 中的所有点。
$x$ 的必经节点集合 $dom(x)$ 就是支配树上 根 $s$ 到 $x$ 路径上的点集。

一些概念

必经点(dom)(割点)

若从 $s$ 到 $t$ 的路径一定经过点 $x$,则称 $x$ 是从 $s$ 到 $t$ 的必经点(割点),记为 $x\quad dom\quad t$。

从 $s$ 出发到达 $t$ 的所有必经点集合为 $dom(t)$,即 $dom(t) = {x | x\quad dom\quad y}$.

最近必经点(idom)

节点 $t$ 的必经点集合 $dom(t)$ 中 $dfn$ 值最大的点 $x$ 是距离 $t$ 最近的必经点,称 $x$ 为 $t$ 的最近必经节点。

最近必经点是唯一的,因此可以记 $x = idom(t)$。

半必经点(semi)

在搜索树 $T$ 上,点 $t$ 的祖先中通过非树边可以到达 $t$ 的且 $dfn$ 最小的祖先 $x$,称为 $t$ 的半必经点。半必经点也是唯一的,因此可以记为 $x = semi(t)$。

半必经点定理

对于 $G$ 中的一点 $t$,考虑所有 $x \in pre(t)$(前驱),定义一个临时变量 $tmp = INF$。

若 $dfn[x] < dfn[t]$,则 $(x,t)$ 为树边或前向边,此时 $tmp = min(tmp, dfn[x])$。

若 $dfn[x] > dfn[t]$,则 $(x,t)$ 为横叉边或后向边,此时 $x$ 的祖先中所有满足 $dfn[z] > dfn[t]$ 的,有 $tmp = min(tmp, dfn[semi[z]])$。

$semi[t] = id[tmp]$,即在上述所有可能情况中取 $dfn$ 值最小的一种,就是 $t$ 的半必经点。

必经点定理

对于 $G$ 中的一点 $x$,考虑搜索树 $T$ 中 $semi(x)$ 到 $x$ 的路径上除端点之外的点构成的集合 $path$。

设 $y$ 为 $path$ 中半必经点的时间戳最小的节点。

若 $semi(x) = semi(y)$,则 $idom(x) = semi(x)$。

若 $semi(x) \neq semi(y)$,则 $idom(x) = idom(y)$

Lengauer-Tarjan 算法:

通过DFS构建搜索树,并计算出每个节点的时间戳。

根据半必经点定理,按照时间戳从大到小的顺序计算每个节点的半必经节点。

根据必经点定理,按照时间戳从小到大的顺序,把半必经节点 $\neq$ 必经节点的点进行修正。

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
// dom[i]:(支配树)编号为i的点所支配的最近节点
// idom[i]:编号为i的点的最近必经节点
// semi[i]:编号为i的点的半必经节点
// id[i]:dfn为i的点的编号
// best[i]:编号为i的点的祖先中dfn最小的点的编号
// pre[i]:编号为i的点的前驱
// suc[i]:编号为i的点的后继
// son[i]:编号为i的点的儿子
struct DomiTree {
int dfs_clock;
int dfn[maxn], id[maxn], fa[maxn];
int semi[maxn], best[maxn], idom[maxn];
vector<int> pre[maxn], dom[maxn], suc[maxn], son[maxn];

void init(int n) {
for (int i = 0; i <= n; i++) {
pre[i].clear(), dom[i].clear(), suc[i].clear(), son[i].clear();
fa[i] = best[i] = idom[i] = semi[i] = i, dfn[i] = 0;
}
dfs_clock = 0;
}
void addedge(int u, int v) {
// u -> v
pre[v].push_back(u);
suc[u].push_back(v);
}
void build(int s) {
dfs(s);
tarjan();
}
void dfs(int u) {
dfn[u] = ++dfs_clock;
id[dfs_clock] = u;
for (auto &v : suc[u]) {
if (dfn[v]) continue;
dfs(v);
son[u].push_back(v);
}
}
inline int Min(int x, int y) { return dfn[semi[x]] < dfn[semi[y]] ? x : y; }

int find(int u) {
if (u == fa[u]) return u;
int v = find(fa[u]);
best[u] = Min(best[fa[u]], best[u]);
return fa[u] = v;
}
void tarjan() {
for (int i = dfs_clock; i > 0; i--) {
int k = id[i];
for (auto v : pre[k]) {
if (dfn[v] == 0) continue;
if (dfn[v] < dfn[k] && dfn[v] < dfn[semi[k]]) semi[k] = v;
if (dfn[v] >= dfn[k]) {
find(v);
semi[k] = semi[Min(best[v], k)];
}
}
if (k != semi[k]) dom[semi[k]].push_back(k);
for (auto &v : dom[k]) {
find(v);
if (semi[best[v]] == k)
idom[v] = k;
else
idom[v] = best[v];
}
dom[k].clear();
for (auto &v : son[k]) fa[v] = k;
}
for (int i = 2; i <= dfs_clock; i++) {
int k = id[i];
if (idom[k] != semi[k]) idom[k] = idom[idom[k]];
if (k != idom[k]) dom[idom[k]].push_back(k);
}
}
} dt;

有向图的必经边(割边)

给定有向图 $G$(可能有环)和图中的一个点 $s$,对于 $G$ 中的任意一个点 $t$,求 $s$ 到 $t$ 路径上(可能有多条)的必经边的集合。

无环图做法

求 $s$ 到每个点的路径数 $Scnt$,$t$ 到每个点的路径数 $Tcnt$。

若边 $(u,v)$ 满足 $Scnt[u] \times Tcnt[v] = Scnt[t]$,那么 $(u,v)$ 是从 $s$ 到 $t$ 的必经边。

可以对几个大质数取模做上述计算。

有环图做法

在 $(u,v)$ 中间加一个点 $w$,然后利用 $Lengauer-Tarjan$ 算法求有向图割点,若 $w$ 是割点,那么 $(u,v)$ 是割边。