CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
====== 连通分量 ======

===== 有向图：强连通分量 =====

强连通分量中的一个点属于且仅属于一个边双连通分量。

缩点时，同一连通分量的点缩成一个点，最终会变成一个 DAG。唯一需要注意的是，重新建图时要判断原边的两个点是否在同一个强连通分量内。

===== 无向图：双连通分量 =====

==== 点双连通分量 ====

点双连通分量删掉任意一个点后仍连通，任意两个点双连通分量至多有一个共同点（因此不会有共同边，否则必然属于同一个分量），且该共同点为割点。一个点可以属于多个点双连通分量。

缩点时，同一连通分量的点缩成一个点，同时保留割点，根据从属关系将分量与割点依次相连。如果把同一连通分量的点都连到对应的割点上，貌似就是一棵圆方树（或森林）了。

特殊地，$K_1,K_2$ 是点双连通分量。

==== 边双连通分量 ====

边双连通分量删掉任意一条边后仍连通，任意两个边双连通分量互不相交（因此不会有共同点，否则必然属于同一个分量），且两个边双连通分量之间以割边链接。一个点最多属于一个边双连通分量（可以不属于任何边双连通分量）。

缩点时，同一连通分量的点缩成一个点，整个图会变成一个树（或森林）。

特殊地，$K_1$ 是边双连通分量。

==== 两种连通分量的关系 ====

  - 点双连通分量一定是边双连通分量（除 $K_2$ 的特殊情况），反之不一定；
  - 点双连通分量可以有公共点，而边双连通分量不能有公共边；
  - 边双连通关系可以传递，但是点双连通关系不行：比如两个三元环有一个共同顶点的图，不属于同一个三元环的任意两个点是边双连通的，但不是点双连通的；

==== 割点与割边的关系 ====

割点和割边没有必然关系：两个端点是割点的边不一定是割边，割边的两个端点也不一定是割点。

下图的 $2, 4$ 是割点，但 $(2, 4)$ 不是割边：

{{ 2020-2021:teams:i_dont_know_png:nikkukun:connected-components-pic1.png }} 

下图的 $(1, 2)$ 是割边，但 $1, 2$ 不是割点：

{{ 2020-2021:teams:i_dont_know_png:nikkukun:connected-components-pic2.png }}



===== 实现中可能遇到的问题 =====

  - 求边双连通分量中存在重边，此时每次向儿子走时不能单纯地不回父亲节点，而是标记父边具体的编号，不选择这条边回去。比如对于有重边的 $K_2$，实际应该是一个边双连通分量。
  - 给定的图不一定连通，需要处理。



===== Reference =====

  - [[https://byvoid.com/zhs/blog/biconnect/|图的割点、桥与双连通分支 - BYVoid]]
  - [[https://blog.aor.sd.cn/archives/418/|点双连通分量 & 圆方树学习笔记 - RainAir]]
  - [[https://blog.csdn.net/qq_39670434/article/details/81973923|Tarjan算法——边双和点双 - 千杯湖底沙. ]]
  - [[https://blog.csdn.net/hailiang70303/article/details/87553759|寒假2019培训：双连通分量（点双+边双） - Purple-Ziy-fire ]]
CVBB ACM Team

用户工具

站点工具

页面工具
