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