割边/桥

定义：删去该边后，原图分裂成大于1个联通块

求解：对于边\(x \rightarrow y\)，若\(low[y] > dfn[x]\)，则\(x \rightarrow y\)是桥

易错：\(dfs\)时，带参数\(faId\)，表示进入\(x\)的边。访问\(x\)到达的点时，略过\(faId\)

边双连通分量

定义：没有割边的极大子图

求解：去除所有割边

充要条件/性质：各边都至少存在于1个简单环中。（若某边仅在简单路径上，则有割边）

割点

定义：删去该点以及与该点相连的边之后，原图分裂成大于1个联通块

求解：

对于非根节点\(x\)，若存在\(x \rightarrow y\)，使得\(low[y] \geq dfn[x]\)，则\(x\)是割点

对于根节点\(rt\)，若\(rt\)的儿子数大于1，则\(x\)是割点

区别：正常的不访问\(fa\)的\(dfs\)

点双联通分量

定义：没有割点的极大子图

求解：\(dfs\)中维护1个栈。若\(x \rightarrow y\)时发现\(x\)为割点，将栈中元素出队至\(y\)。这些元素与\(x\)共同构成点双联通分量

区别：一个割点可能属于多个点双联通分量

充要条件/性质：任意两点都至少包含在1个简单环中。（假设两点间只有简单路径，则有割点）

应用

通过缩点等处理，简化问题

例题

AcWing 365

题意

给定1张\(n\)点\(m\)边的无向连通图，求解不在任何1个奇环中的点的个数。

\(1 \leq n \leq 1000 , 1 \leq m \leq 10^6\)

题解

引理1：不属于同1点双联通分量的点之间不可能存在环

简略证明：存在环，则环中没有割点，则可以合并点双联通分量，与极大性矛盾

引理2：在同1点双联通分量中，若存在1个奇环，则所有点都在至少1个奇环中

简略证明：若存在1个奇环，对于奇环外的任意点\(x\)，一定能够跟该奇环上的2点形成至少1个环。（反证：若仅有简单路径，则该简单路径上有割点）。由此，奇环被分割成长度奇偶性不同的两部分，其中1个部分一定能跟\(x\)组合形成奇环。

由此，只需求出所有的点双联通分量，并在各个点双联通分量中通过染色法判定是否存在奇环。若不存在，累加点双联通分量的大小即可。时间复杂度\(O(n + m)\)。代码见此