szzjz WiKi连通性相关
边双基本性质
- 任意两点之间的所有路径的必经边
- 任意两点之间的所有路径的必经边（所有路径边集的交） = 两点之间任意一条简单路径经过的割边 = 边双缩点树上两点所在点的路径长。
- 边双连通关系
- (x,y) 边双连通意味着任何一条边割去后 (x,y) 仍然连通。
- 点与边的归属
- 任何一个点恰属于一个边双。
- 任何一条边要么属于一个边双，要么是割边。
- 边双缩点树的连通性
- 边双缩点树割去一条边后点的连通性和原图中割去该边的连通性相同。
- 边双的传递性
- 边双具有传递性，即若 (a,b) 边双连通，(b,c) 边双连通，则 (a,c) 边双连通。
点双基本性质
- 任意两点之间所有路径的必经点
- 任意两点之间所有路径的必经点（所有路径点集的交） = 圆方树上两点之间路径的原点个数，且不等于两点之间任意一条简单路径上的割点个数。
- 圆方树的性质
- 圆方树是无根树。
- 割点的判定
- 一个点是割点，当且仅当该点是两个点双的交，且该点在圆方树上不是叶子节点。
- 边与方点的关系
- 任何一条边恰属于一个方点（点双）。
- 圆方树割点后的连通性
- 圆方树割去一个点后点的连通性和原图中割去该点的连通性相同。
- 点双的传递性与分类
- 点双不具有传递性。
- 点双的分类：
- 点数 = 2：特殊情况，一般需要单独考虑。
- 点数 > 2：一般情况，重点考虑此类。
一些涉及存在性的性质
边双与点双的回路和环性质
下面的点双不考虑点数 = 2 的特殊情况。
- 边双中任意两点有回路（不保证点不交，但保证边不交）。
- 点双中经过任意两点/任意一点一边/任意两边有简单环。
Menger 定理
- 无向图上任意不同的两点不连通所需删去的边的数量的最小值 = 两点之间边不相交的迹的数量的最大值。
- 无向图上任意不同且不相邻的两点不连通所需删去的点的数量的最小值 = 两点之间点不相交（不在除了这两点以外的点相交）的路径数量的最大值。
- 证明：最大流最小割定理。
点双中的路径性质
- 点双中任意两点 (x,y) 和任意一边 (e)，存在 (x\rightarrow e\rightarrow y) 的简单路径。
- 点双中任意三点 (x,y,z)，存在 (x\rightarrow y\rightarrow z) 的简单路径。
求边双（割边）
- low[x] 的本质 注意 (low[x]) 的本质是 dfs 树中 (x) 子树的非树边能覆盖到的最浅祖先。当然，树上差分也可以处理覆盖。
- 割边的判定 根据 Menger 定理，被覆盖了的树边必然不是割边，而割边必然是树边，所以这样求是对的。
- 边双的处理 边双在 dfs 树上是占据了一个连通块，所以可以通过栈来处理。每次判定当前已经到了一个边双（所在连通块）的最高点，就将当前边双 pop 出去。
求点双
原理类似边双。求割点注意根节点必须有两个儿子（不是叶节点）才是割点。
tarjan 求强连通分量（有向图 dfs 树相关）
- 有向图 dfs 树的边类型 在分析强连通分量时，因为其定义，所以从任意一点开始用 dfs 考虑。有向图的 dfs 树中有四种边：树边，返祖边，前向边，横叉边。其中，前向边对于连通性没有影响，可以暂时不管。
- 返祖边与横叉边的作用
- 返祖边能让边到的祖先和当前点的路径上的所有点都进入 SCC。
- 重点看横叉边，其有用当且仅当其能到当前点的祖先（通过若干横叉边，返祖边）。
- SCC 的处理与 low[x] 的维护
- SCC 在 dfs 树上仍然是占据了一个连通块，所以还是通过栈来处理，想办法在最高点做出判定。发现，核心还是在返祖边，而横叉边是传递作用。所以还是考虑维护当前节点 (x) 能到的最高祖先的 (dfn)，即 (low[x])。
- 首先直接对儿子的最高祖先取 (min)，然后考虑当前节点的返祖边直接取 (dfn) 作 (chkmi)，前向边不作更新。
- 而横叉边首先保证能到当前节点的祖先，可以发现如果能到某个祖先 (y)，那么 (y) 一定是该横叉边两端点的 (lca) 的祖先，所以这些点一定还保存在栈中，记录一下每个节点是否在栈中，在的话才要取其 (low) 作 (chkmi)。
- 最高点的判定 最高点的判定就是 (low[x] == dfn[x])，及时 pop。当然，我们发现横叉边也可以取 (dfn) 作判定，前向边也可以不特判，效果一样。
- 模板与扩展
- 我们常写的模板是最简洁的版本，事实上可以有多种实现。
- 扩展：取产生每个 SCC 的顺序的反序就是拓扑序。
- 证明：一棵 dfs 树肯定是对的，多棵之间连接也是有序的（否则就会变成一棵）。
kosaraju 求强连通分量
szzjz 此处未详细展开相关内容。