割点和桥 一、定义 割点和桥都是无向图中的概念。
割点:对于无向图,删除该点及其出边之后图的连通分量增加了,这个点就是割点,又称为割顶。
桥:对于无向图,删除该边之后,图的连通分量增加了,这个点就是桥。
二、原理 割点和桥都可以使用 tarjan 算法求解。
割点 使用 tarjan 算法求割点,对于割点 $u$ ,需要存在孩子节点 $v$ ,满足 $low[v]\ge dfn[u]$ ,满足该条件的为割点。特殊的是,如果一个点为根,并且有多于两棵子树,则该根节点也为割点。
如上图, $low[v] \ge dfn[u]$ 表示在 $u$ 为根的子树中,子树中的节点 $v$ 最远能够到达的祖先不能高于 $u$ ,最多只能到 $u$ ,因此 $u$ 显然就是一个割点。大于的情况如下所示:
如果为根节点,在遍历时需要记录子树的数量,在后续遍历的位置判断子树的数量是否大于 $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$ 这条边为桥。
单个的链也是桥。
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]