连通分量

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

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

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

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

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

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

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

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

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

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

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

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

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

1. 图的割点、桥与双连通分支 - BYVoid
2. 点双连通分量 & 圆方树学习笔记 - RainAir
3. Tarjan算法——边双和点双 - 千杯湖底沙.
4. 寒假2019培训：双连通分量（点双+边双） - Purple-Ziy-fire