线性时间查找图中的所有node-cut

node-cut定义:

对于一个无向图$G$,如果删除一个点$v$可以增加联通分支的数量,那么我们称点$v$是图$G$的一个node-cut,即点分割。(注意和最小割是有区别的,最小割是用移除最少了边使得原图不联通,可以用流算法去解决)

node-cut的性质:

对于点$p$,如果存在一个子节点$q$,在$q$点的DFS搜索树上如果没有存在反向边指向DFS搜索中$p$的祖先节点,那么对于这样的$p$点是原图的node-cut。

基于这样的性质,我们可以用一次DFS来找出原图的所有node-cut,具体的一些设定可以参考《算法导论》图算法部分的DFS章节:(白色节点表示未被访问过,灰色节点表示第一次访问到,黑色节点表示访问结束):时间复杂度是$O(V+E)$

DFS过程中每个节点增加一个变量ctime(v),默认为-1,记录自身或者DFS搜索树中子节点指向DFS点中灰色点u最小的d(u)。当p点结束DFS搜索由灰变黑时,将ctime(p)传递给DFS父节点q,如果$ctime(p)<ctime(q)$,$ctime(q):=ctime(p)$。当一个点v从灰变成黑时,可以根据ctime(v)和ctime(v)比较判断自身是否是node-cut。

附:DFS的root结点需要单独判断,如果dfs生成树的子节点数量大于等于2,那么根节点为cut-node,反之不为cut-node。

上述性质来自这篇paper:

A Silent Self-Stabilizing Algorithm for finding Cut-nodes and Bridges

这篇paper还给出了另外找node-cut的算法,有点长不大想看就自己想了一个算法。

2016年8月26日更新算法实现:

cut-node线性算法的实现