實(shí)在坑爹，網(wǎng)上沒什么人把這事講的清楚，基本上是一些抄別人代碼的貨。
無向圖的點(diǎn)雙聯(lián)通，邊雙聯(lián)通，求割點(diǎn)，橋(割邊)
有向圖的強(qiáng)聯(lián)通分量，有向圖的割點(diǎn)，有向圖的橋這倆和求無向圖沒啥區(qū)別。
其實(shí)，這些問題總結(jié)成一句話就是求環(huán)。然后再根據(jù)環(huán)來判斷相應(yīng)的情況。其實(shí)這些東西算法導(dǎo)論上講的比較明顯和清楚，但是限于他講的還不在我的理解范圍之內(nèi)，所以看了一遍沒看懂糾結(jié)了好多天弄了幾個題之后，發(fā)現(xiàn)那上面的寫法非常明了。好了下面就說說每種怎么求。
首先是無向圖的點(diǎn)雙連通。點(diǎn)雙連通就是說這個點(diǎn)可以通過dfs樹的子節(jié)點(diǎn)鏈接到父節(jié)點(diǎn)上面去。我們只要求每個點(diǎn)的子節(jié)點(diǎn)不通過父親節(jié)點(diǎn)連接到當(dāng)前vis[v]=1的最小編號就可以了。這樣所有的雙連通的點(diǎn)的low都是一樣的。這里有個非常非常細(xì)微的一點(diǎn):如果某個父親點(diǎn)是割點(diǎn)，并且它又鏈接到了更高層的父親，那么當(dāng)刪除這個父親點(diǎn)的時候，圖就變成兩個不連通的子圖了。所以我們在判斷的時候，當(dāng)某個點(diǎn)連接到vis[v] = 1的點(diǎn)的時候，low[u] = min(low[u],dfn[v]);這里就是為了防止v是割點(diǎn)。而當(dāng)求邊雙連通的時候，就可以不管這些，因為刪掉了邊那個點(diǎn)還在，所以無所謂：low[u] = min(low[u],low[v])。用算法導(dǎo)論上面白色點(diǎn)，灰色點(diǎn)，黑色點(diǎn)標(biāo)記的方法很容易理解這些看起來復(fù)雜的玩意。
其次是求割點(diǎn)和割邊。神奇的是，這兩個玩意的求法和點(diǎn)雙連通邊雙連通大致是相同的。割點(diǎn)的話，如果它所有的孩子都能連接到父親點(diǎn)以上（注意上一段哦），那么可以，否則不可以。割邊比這個簡單點(diǎn)，有向邊(u,v)如果v點(diǎn)可以不通過樹邊連接到父親點(diǎn)和父親點(diǎn)以上，那么就是割邊。大概就是這樣子，具體的細(xì)節(jié)自己想下就好了。關(guān)鍵就是那個通過自己繞到父親點(diǎn)是一個比較麻煩的地方。
然后是有名的求有向圖的強(qiáng)連通分量算法。其實(shí)這個算法已經(jīng)說過了，就是求無向圖的邊雙連通的算法。一個節(jié)點(diǎn)的子節(jié)點(diǎn)通過邊繞到最高的灰色節(jié)點(diǎn)上就可以了。我們也不用考慮什么割點(diǎn)啊什么的了。實(shí)際上一個極大強(qiáng)連通分量就是環(huán)套環(huán)，那么我們把這個環(huán)里面每個點(diǎn)都找到可以繞到的dfn最小的節(jié)點(diǎn)即可。
說了這么多里面有很多細(xì)節(jié)要注意，而且求有向圖的強(qiáng)連通分量算法可以寫得更簡單，不用弄個棧來糊弄人的。只要求出low數(shù)組就一切OK了。算導(dǎo)的好處就是寫的很經(jīng)典，壞處就是說的很少。所以需要把很多東西有過一定的了解和對比之后再看才有意義。同時找題解的過程發(fā)現(xiàn)了許多人的代碼寫得很簡介優(yōu)美，比主流的寫法好很多，我想說代碼反映了一個人的思維過程。
下次把幾個求各種聯(lián)通的模板補(bǔ)一下，看看能不能寫出點(diǎn)自己滿意的代碼出來。
以上。