用户工具

站点工具


2020-2021:teams:i_dont_know_png:potassium:connected_component

这是本文档旧的修订版!


连通分量

强连通分量

只有有向图才有这种定义,强连通分量中,点两两可达。

SCC 主要用于缩点,每一个点仅属于一个 SCC。缩点后是一个 DAG ,在建新图过程中需要注意两点不应属于同一 SCC 。

实现中,在遍历到 $p\rightarrow q$ 返祖边时,对于 low[p] 的更新, min(low[p],low[q])min(low[p],dfn[q]) 等价,均可正确计算出结果。这与点双连通分量是不同的。

模板题:缩点

点双连通分量

一个点双删掉任意点后图仍然连通。注意,根据此定义,K1 和 K2 均为点双。

v-DCC 主要用于判割点,每一个非割点仅属于一个 v-DCC ,割点可以同时属于多个 v-DCC 。

实现中,如果某个点 p 是割点,它应当满足以下条件之一:

  1. p 是根节点,且以它为根的 dfs 树有大于一个分支;
  2. p 不是根节点,且它的某个孩子 q 不能返祖(即 low[q]>=dfn[p] )。

由于求 DCC 是通过某个有孩子的割点进行判定的,故需要对孤立点进行特判。

模板题:点双 割点

边双连通分量

一个边双删掉任意边后图仍然连通。

无向图中的 e-DCC 和有向图中的 SCC 很相似,有的时候可以进行缩点。

实现中, e-DCC 和 SCC 的实现方式也类似,只是加了一个不能走父边的限制。

模板题:边双

杂项

割点和割边没有任何联系,除了他们姓一样:

割边两段不一定是割点:

两割点不一定组成割边:

2020-2021/teams/i_dont_know_png/potassium/connected_component.1589485049.txt.gz · 最后更改: 2020/05/15 03:37 由 potassium