Zth's Blog

记录学习路上的点滴

0%

Tarjan算法与图的连通性

参考lyd《算法竞赛进阶指南》

Tarjan算法与无向图连通性

一些概念

割点和桥

给出无向连通图$G = (V, E)$

​ 若对于$x \in V$, 从图中删去$x$以及所有与$x$相关的边之后, $G$分解为两个或两个以上不相连的子图, 则称$x$为$G$的一个割点

​ 若对于$e \in E$, 从图中删去边$e$之后, $G$分裂为两个不相连的子图, 则称$e$为$G$的一条割边或桥

时间戳

在图的深度优先遍历中, 按照每个节点第一次被访问的时间顺序, 一次给予$N$个节点$1 … N$的整数标记, 该标记就被叫做时间戳, 用$dfn[x]$来表示

搜索树

在无向连通图中任选一个节点出发进行深度优先遍历, 每个节点只访问一次。 所有发生递归的边$(x, y)$(即从$x$到$y$是对$y$的第一次访问)构成一棵树, 我们把它称为无向连通图的搜索树。 如果图本身不连通, 则会出现一个搜索森林

追溯值

$Tarjan$算法引入一个追溯值$low[x]$。 设$subtree(x)$表示搜索树中以$x$为根的子树。 $low[x]$定义为以下节点的时间戳的最小值

  1. $subtree(x)$中的节点
  2. 通过$1$条不在搜索树中的边, 能够到达$subtree(x)$的节点

根据定义, 为了计算$low[x]$, 先令$low[x] = dfn[x]$, 然后考虑从$x$出发的每条边$(x, y)$

  1. 在搜索树上$x$是$y$的父节点, 则令$low[x] = min(low[x], low[y])$
  2. $(x, y)$不是搜索树上的边, 则令$low[x] = min(low[x], dfn[y])$

割边判定法则

无向边$(x, y)$是桥, 当且仅当搜索树上存在$x$的一个子节点$y$, 满足$dfn[n] < low[y]$, 即从$y$出发, 不能回到$x$或者早于$x$的节点, 那么删去这条边, $x$与$y$将不再连通

显然, 桥一定是搜索树上的边, 并且简单环上的边都不是桥

代码

与求解割点的代码类似, 所以这里不特别给出, 只需注意$tarjan函数$中传参额外传一个入边的编号而不是父节点编号以应对重边的情况, 建边时边的编号使用成对存储

割点判定法则

若$x$不是搜索树的根节点, 则$x$是割点当且仅当搜索树上存在$x$的一个子节点$y$满足$dfn[x] \leq low[y]$, 即$y$不能追溯到早于$x$的节点, 删去$x$, $y$将与其所有祖先节点不可达

若$x$是搜索树的根节点, 则$x$是割点当且仅当$x$有两个或两个以上的子节点

代码

题目为洛谷模板题

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
77
78
79
80
81
82
#include <iostream>
#include <cstdio>

int n, m;
int tot, head[20004];
struct Edge
{
int from, to, next;
} edge[200005];
int num, dfn[20004], low[20004];
int root;
bool cut[20004];
int cnt;

void Addedge(int u, int v)
{
edge[++ tot] = (Edge){u, v, head[u]};

head[u] = tot;
}

void Tarjan(int u)
{
low[u] = dfn[u] = ++ num;

int child = 0;
bool is_root = (u == root);

for(int i = head[u]; i; i = edge[i].next)
{
int v = edge[i].to;

if(! dfn[v])
{
child ++;

Tarjan(v);

low[u] = std:: min(low[u], low[v]);

if(is_root == false && low[v] >= dfn[u])
{
if(! cut[u]) cnt ++;

cut[u] = true;
}
}
else
low[u] = std:: min(low[u], dfn[v]);
}

if(is_root && child > 1)
{
if(! cut[root]) cnt ++;

cut[root] = true;
}
}

int main()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; i ++)
{
int u, v;

scanf("%d%d", &u, &v);

Addedge(u, v);
Addedge(v, u);
}

for(int i = 1; i <= n; i ++)
if(! dfn[i])
root = i, Tarjan(i);

printf("%d\n", cnt);
for(int i = 1; i <= n; i ++)
if(cut[i]) printf("%d ", i);

return 0;
}

Tarjan算法与有向图连通性

一些概念

流图

给定有向图$G = (V, E)$, 若存在$r \in V$, 满足从$r$出发能到达$V$中所有的点, 则称$G$是一个流图(Flow Graph), 记为$(G, r)$, 其中$r$称为流图的源点

搜索树

在一个流图$(G, r)$上从$r$出发进行深度优先遍历, 每个点只访问一次。 所有发生递归的边$(x, y)$, 构成一棵以$r$为根的树, 我们把它称为流图$(G, r)$的搜索树

时间戳

在深度优先遍历中, 按照每一个节点第一次被访问的时间顺序, 依次给予流图中的$N$个节点$1 … N$的整数标记, 该标记称为时间戳, 记为$dfn[x]$

流图中的每条有向边$(x, y)$可以分为四类

  1. 树枝边, 指搜索树中的边, 即$x$是$y$的父节点
  2. 前向边, 指搜索树中$x$是$y$的祖先节点
  3. 后向边, 指搜索树中$y$是$x$的祖先节点
  4. 横叉边, 指除了以上三种情况之外的边, 它一定满足$dfn[y] < dfn[x]$

有向图的强连通分量

给定一张有向图, 若对于图中的任意两个节点$x, y$, 既存在从$x$到$y$的路径, 也存在$y$到$x$的路径, 则成该有向图是强连通图

有向图的极大强连通子图被称为强连通分量, 简称为SCC

追溯值

设$subtree(x)$表示流图的搜索树中以$x$为根的子树。 $x$的追溯值定义为满足以下条件的节点的最小时间戳

  1. 该点在栈中
  2. 该点不在栈中, 存在一条从$subtree(x)$出发的有向边, 以该点为终点

根据定义, 我们按照如下方法计算追溯值

  1. 当节点$x$第一次被访问时, 把$x$入栈, 初始化$low[x] = dfn[x]$

  2. 扫描从$x$出发的每条边$(x, y)$

    (1)若$y$没有被访问过, 则说明$(x, y)$是树枝边, 递归访问$y$, 从$y$回溯之后, 令$low[x] = min(low[x], low[y])$

    (2)若$y$被访问过并且$y$在栈中, 则令$low[x] = min(low[x], dfn[y])$

    ​ PS: 存在$y$被访问过但是$y$不在栈中的情况, 此时$(x, y)$为横叉边

强连通分量判定法则

在追溯值计算的过程中, 若从$x$回溯前, 有$low[x] = dfn[x]$成立, 则栈中从栈顶到$x$的所有节点构成一个强连通分量

因为$x$不能追溯到其前面的点, 也已经从$x$搜索找到了所有可达的点, 而栈中所有的点都可追溯到$x$(如果栈中有点不能追溯到$x$, 那它应该在回溯到$x$前已经被弹出栈了)

代码

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
void Tarjan(int u)
{
dfn[u] = low[u] = ++ p;
S.push(u);
vis[u] = true; // vis表示是否在栈

for(int i = head[u]; i; i = edge[i].next)
{
int v = edge[i].to;

if(! dfn[v])
Tarjan(v), low[u] = std:: min(low[u], low[v]);
else if(vis[v])
low[u] = std:: min(low[u], dfn[v]);
}

if(dfn[u] == low[u])
{
while(S.top() != u)
{
int now = S.top();

S.pop();
vis[now] = false;
}

S.pop();
vis[u] = false;
}
}

需要注意的是第$14$行代码, 如果写成low[u] = std:: min(low[u], low[u])也是对的, 不过如果严格根据定义, 不应该这样写

如果在割点和桥的时候这样写, 会出错, 因为不满足了追溯值的定义

如上图所示, 节点编号即为其$dfn$, 绿色的边为搜索树上的边

如果我们的写法是low[u] = std:: min(low[v], low[u]), 在进行完红圈的搜索后, 由于$low[5] = 2$, 回溯到$3$时会有$low[4] = 2, low[3] = 2$, 然后进行蓝圈的搜索会有$low[7] = low[6] = 2$, 这个时候$3$号点就不会被判断为割点, 因为$6, 7$通过它的另一个环找到了比它更早的点, 这显然是错误的, 和我们定义的通过$1$条不在搜索树上的边冲突, 所以出错也是理所应当