点的双连通分量分为两步
1.如何求割点
O x low(y)>=dfn(x)时分情况讨论
/ 1.如果不是根节点,那就是
O y 2.如果是根节点,当连接在其上的V-DCC数量大于1时,则是一个割点。
2.如何求双连通分量
if(dfn[x]<=low[y])
{
cnt++;//连接在该割点上的V-DCC数量
if(x非根节点||cnt>1) x是割点
将栈中元素弹出直至弹出y为止
且x也属于该"点双连通分量"
}
细节
1.点双连通分量
的栈弹出位置与强连通分量
和边的双连通分量
不同。
它是在当发现这是一个割点的时候,将栈内所有元素弹出,只剩割点。
2.点双连通分量在进行缩点操作的时候,是将每一个割点所在的两个V-DCC向割点连一条边
O---O O <- V-DCC
\ / |
O <- 割点 缩点后 O <- 割点
/ \ |
O---O O <- V-DCC