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