0%

割点和桥

割点和桥

一、定义

割点和桥都是无向图中的概念。

割点:对于无向图,删除该点及其出边之后图的连通分量增加了,这个点就是割点,又称为割顶。

桥:对于无向图,删除该边之后,图的连通分量增加了,这个点就是桥。

二、原理

割点和桥都可以使用 tarjan 算法求解。

割点

使用 tarjan 算法求割点,对于割点 $u$ ,需要存在孩子节点 $v$ ,满足 $low[v]\ge dfn[u]$ ,满足该条件的为割点。特殊的是,如果一个点为根,并且有多于两棵子树,则该根节点也为割点。

image-20230526182640427

如上图, $low[v] \ge dfn[u]$ 表示在 $u$ 为根的子树中,子树中的节点 $v$ 最远能够到达的祖先不能高于 $u$ ,最多只能到 $u$ ,因此 $u$ 显然就是一个割点。大于的情况如下所示:

image-20230526183145773

如果为根节点,在遍历时需要记录子树的数量,在后续遍历的位置判断子树的数量是否大于 $1$ ,大于 $1$ 则为割点。

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
bool ans[maxn];
int dfn[maxn], low[maxn], dfn_clock = 0;
void tarjan(int u, int fa, bool isRoot)
{
low[u] = dfn[u] = ++dfn_clock;
int child_cnt = 0;
for (int i = 0; i < g[u].size(); ++i)
{
int v = g[u][i];
if (!dfn[v])
{
tarjan(v, u, false);
low[u] = min(low[u], low[v]);
if (!isRoot && low[v] >= dfn[u])
ans[u] = true;
++child_cnt;
}
else
{
if (v != fa)
low[u] = min(low[u], dfn[v]);
}
}
if (isRoot && child_cnt >= 2)
ans[u] = true;
}

写代码时,也可以不用 isRoot,对根节点传入 fa = u,判断根节点时只用判断 fa == u 就行了。

使用 tarjan 算法求桥,对于桥 $e=\{u,v\}$ ,需要满足 $low[v] \gt dfn[u]$ , $u$ 的孩子节点如果满足该条件则 $u\rightarrow v$ 这条边为桥。

image-20230526184427352

单个的链也是桥。

image-20230526205737346

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void tarjan(int u, int fa)
{
dfn[u] = low[u] = ++dfn_clock;
for (int i = 0; i < g[u].size(); ++i)
{
int v = g[u][i].first;
int w = g[u][i].second;
if (!dfn[v])
{
tarjan(v, u);
low[u] = min(low[u], low[v]);
if (low[v] > dfn[u])
{
ans = min(ans, w);
}
}
else if(v != fa)
{
low[u] = min(low[u], dfn[v]);
}
}
}

使用链式前向星更方便一些,链式前向星可以把所有的边存起来,如果一个边是桥,可以方便的打标记。

例题:

P3388 【模板】割点(割顶) | Luobuyu’s Blog

4738.Caocao’s Bridges | Luobuyu’s Blog

参考链接:

为什么else里面不能用low[v]更新,必须得用dfn[v]

image-20230526215128331