割点
对于一张无向图 \(G=(V,E)\),使得 H 是 G 的连通子图,且不存在 \(F\) 满足 \(H \subsetneq F \in G\) 且 \(F\) 为连通图,则称 \(H\) 是 \(G\) 的一个连通块/连通分量(connected component),又叫极大连通子图。
由此,我们可以对割点做出如下定义:
对于一个无向图,如果把一个点删除后这个图的极大连通分量数增加了,那么这个点就是这个图的割点(又称割顶)。
Tarjan
处理过程
与有向图的强连通分量相似,我们定义如下两个重要数组:
dfn[]
:表示深度优先遍历图时节点 \(u\) 被遍历到的次序,即时间戳。low[]
:节点 \(u\) 在不通过父亲走过的路的情况下可以到达节点的最小时间戳。
根据割点的定义可知,如果一个节点 \(ver\) 是割点,那么必然有一个处于其 DFS 序子树内的节点 \(to\) 使得:
\[low_{to} \ge dfn_{ver} \]这个意思指的是无论如何走,\(to\) 都无法到达 \(ver\) 以上的节点,不能回到祖先,那么 \(ver\) 即为割点。
然而当 \(ver\) 作为搜索的起始点时,由于 \(ver\) 以上没有父亲节点,自然无法判断其是否是割点,这种方法并不适用,对于这种情况,我们可以直接特判:记录从 \(ver\) 节点开始可以到达的子节点数量,如果大于 \(1\),则 \(ver\) 肯定是割点;而如果只有一个儿子的话,删掉 \(ver\) 不会发生任何影响。
考虑如何在搜索的过程不断更新 low[]
数组:
-
当遍历到当前点 \(ver\) 时,令 \(low_{ver} \gets dfn_{ver}\)。
-
遍历子节点 \(to\) 时,如果 \(to\) 已经被更新过(\(dfn_{to}\) 有值),那么边 \(ver \to to\) 为非树边,要么为前向边(我们不用处理),要么为返祖边(令 \(low_{ver} \gets dfn_{to}\))。
-
否则,由于 \(to\) 没有被遍历过,在 \(ver\) 的搜索子树当中,我们继续搜索 to 的子树,并将传递的值返回,令 \(low_{ver} \gets \min(low_{ver}, low_{to})\)。
伪代码如下(摘自 OI Wiki):
\[\begin{array}{ll} 1 & \textbf{if } v \text{ is a son of } u \\ 2 & \qquad \text{low}_u = \min(\text{low}_u, \text{low}_v) \\ 3 & \textbf{else} \\ 4 & \qquad \text{low}_u = \min(\text{low}_u, \text{dfn}_v) \\ \end{array} \]注意
由于 low[]
数组在 DFS 序子树中具有传递性,直接在子树中传递 low[ver] = min(low[ver], low[to])
是没有任何问题的。
而如果边 \(ver \to to\) 是一条返祖边时,采取 low[ver] = min(low[ver], low[to])
的更新方式会使得之后的点可以回溯到 \(ver\) 的其他点更新时重复上跳,违反了 low[]
数组的初始定义,导致出错。况且 low[]
数组的核心用处是判断 \(low_{to} \ge dfn_{ver}\) ,并非求最值,它仅需要找到一个比 \(ver\) 更小的点即可,因此 low[ver] = min(low[ver], dfn[to])
的正确性成立。
代码
给出一个 \(n\) 个点,\(m\) 条边的无向图,求图的割点。
void tarjan(int ver, int pre)
{
dfn[ver] = low[ver] = ++ timestamp; // 初始化时间戳
int child = 0; // 记录该节点为根有几个儿子
for (int i = h[ver]; ~i; i = ne[i])
{
int j = e[i];
if (!dfn[j])
{
child ++;
tarjan(j, ver);
low[ver] = min(low[ver], low[j]);
if (ver != pre && low[j] >= dfn[ver] && !flag[ver])
res ++, flag[ver] = true; // 找到一个割点
}
else if (j != pre)
low[ver] = min(low[ver], dfn[j]);
}
if (ver == pre && child >= 2 && !flag[ver])
res ++, flag[ver] = true; // 特判根节点
}
割边(桥)
与割点的定义类似,如下:
对于一个无向图,如果删掉一条边后图中的连通分量数增加了,则称这条边为桥或者割边。
Tarjan
处理过程
与 Tarjan 算法求解割点的方法类似,我们同样定义两个数组 dfn[]
和 low[]
处理,对于一条割边,以它连接的子树必然无法通过别的边到达它上面的点,即对于一条在 DFS 树上的 \(ver \to to\) 边 \(edge\):
需要注意的是,在标记一条边时,同时要标记它的反边。
代码
void tarjan(int ver, int from)
{
dfn[ver] = low[ver] = ++ timestamp;
for (int i = h[ver]; ~i; i = ne[i])
{
int to = e[i];
if (to == (from ^ 1)) continue;
if (!dfn[to])
{
tarjan(to, i);
low[ver] = min(low[ver], low[to]);
if (low[to] > dfn[ver])
bridge[i] = bridge[i ^ 1] = true, ++ ans;
}
else low[ver] = min(low[ver], dfn[to]);
}
}
Reference
P3388 【模板】割点(割顶) - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
图论基础 - qAlex_Weiq - 博客园 (cnblogs.com)
标签:ver,min,割点,笔记,dfn,low,节点,模板 From: https://www.cnblogs.com/ThySecret/p/18524698