割点和桥

定义

  • 割点: 对于一个图,如果删掉点$u$和与其连接的所有边之后,该图联通块个数增加,则称该点$u$为该图的割点(割顶)
  • 桥: 对于一个图,如果删掉边$(u,v)$该图联通块个数增加,则称该边$(u,v)$为该图的桥

割点

通常使用$Tarjan$算法求解

设两个数组$low$和$dfn$,定义$dfn[u]$表示$u$在搜索树中被遍历的次序(即时间戳),$low[u]$为$u$或$u$的子树所能一次遍历到的最早的搜索树中的节点的$dfn$值

另外$Tarjan$过程中会遇到三种边: 树枝边、前向边、后向边(与有向图求强连通分量的定义类似)

根据定义则有

  • 若$(u,v)$为树枝边,$u$为$v$的父节点,则$low[u]=min(low[u],low[v])$
  • 若$u,v$为后向边,$v$不为$u$的父节点,则$low[u]=min(low[u],dfn[v])$

则对于一个点是割点,当且仅当满足以下条件中的一个

  • 若$u$为树的根节点,且$u$有多于一个子树
  • 若$u$不为树的根节点,且满足存在$(u,v)$的树枝边,并使得$dfn[u]<=low[v]$(即删去$u$后$v$以及$v$的子树不能到达$u$的祖先)

模板题:P3388 【模板】割点(割顶)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
inline void Tarjan(int u)
{
dfn[u] = low[u] = ++ sum;
int cnt = 0; // 计算儿子个数
for ( int i = Begin[u]; i; i = Next[i] )
{
int v = To[i];
if ( !dfn[v] )
{
Tarjan(v); ++ cnt; low[u] = min(low[u], low[v]);
if ( (u == root && cnt > 1) || (u != root && dfn[u] <= low[v]) ) cut[u] = 1; // 是割点
}
else low[u] = min(low[u], dfn[v]);
}
}

一条无向边$u,v$是桥,当且就当$(u,v)$是树枝边且满足$dfn[u]<low[v]$(因为$v$想要到达$u$的父亲必须经过$(u,v)$这条边)

实现时有些麻烦,在判断是否为后向边时需要注意判断是树枝边的反向边还是新的一条边

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
inline void add(int u, int v)
{
To[++ e] = v; Next[e] = Begin[u]; Begin[u] = e; be[e] = e + 1; // 需要将一条无向边变为两条编号相同的无向边
To[++ e] = u; Next[e] = Begin[v]; Begin[v] = e; be[e] = e - 1;
}

inline void Tarjan(int u)
{
low[u] = dfn[u] = ++ cnt; Stack.push(u);
for ( int i = Begin[u]; i; i = Next[i] )
{
vis[i] = true;
if ( !vis[be[i]] ) // 判断后向边时是树枝边的反向边还是新的一条边
{
int v = To[i];
if ( !dfn[v] ) { Tarjan(v); low[u] = min(low[u], low[v]); }
else low[u] = min(low[u], dfn[v]);
}
}
}

双联通

这个就直接写结论,答案为缩点后(叶子节点个数+1)/2