Tarjan算法与无向图连通性

割边/桥

定义:删去该边后,原图分裂成大于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)\)。代码见此

上一篇:岭回归(Ridge Regression)和Lasso回归


下一篇:透彻tarjan