最近想了好久没想出来,希望高手给我写一个求图的点割集和边割集的Java代码,感激不尽~
在深度优先树中,根结点为割点,当且仅当他有两个或两个以上的子树。
其余结点v为割点,当且仅当存在一个v的后代结点s,s到v的祖先结点之间没有反向边。
记发现时刻dfn(v)为一个节点v在深度优先搜索过程中第一次遇到的时刻。
记标号函数low(v) = min(dfn(v), low(s), dfn(w))
s是v的儿子,(v,w)是反向边。
low(v) 表示从v或v的后代能追溯到的标号最小的节点。
则非根节点v是割点,当且仅当存在v的一个儿子s,low(s) >= dfn(v)
网上抄的 :wink: