目錄
一、無向圖割點、橋、雙連通分量
Tarjan 算法求割點和橋（割邊）
“割點”代碼
邊雙和點雙連通分量
邊雙連通分量 和 點雙連通分量 的縮點
二、有向圖強連通分量
1.有向圖的弱連通與強連通
2.強連通分量
Kosaraju算法
Tarjan 算法（求強連通分量）
一、無向圖割點、橋、雙連通分量
- 給定無向連通圖 G = (V, E)
- 對于一個點 x，若從圖中删除 x 及所有與 x 相連的邊，圖不再連通，x 是 G 的割點
- 對于一條邊 e，從圖中删去 e，圖不再連通， e 是 G 的割邊
- 一個圖如果不存在割點，則它是一個點雙連通圖，一個圖的極大點雙連通子圖是它的點雙連通分量。
- 一個圖如果不存在割邊，則它是一個邊雙連通圖，一個圖的極大邊雙連通子圖是它的邊雙連通分量。
先借用OI Wiki (傳送門)的圖解釋幾種邊：
Tarjan 算法求割點和橋（割邊）
- 時間戳 dfn：第幾個搜到這個點
- 返祖邊：搜尋樹上一個點連向它另一條支鍊上的點的邊
- （橫插邊：在搜尋樹上一個點連向它另一條支鍊上的點的邊——在無向圖中不存在【因為下一條支鍊在dfs序中會直接接在目前這條支鍊後面成為“子樹”】
- 追溯值 low：目前點及其子樹通過一條返祖邊能連到的最小 dfn 值
- 如果 <u, v> 是搜尋樹的邊：low[u] = min(low[u], low[v])
- 如果 <u, v> 是返祖邊：low[u] = min(low[u], dfn(v))
下面來看一個連通圖，尋找割點和割邊（橋）所滿足的規律。右圖為左圖的一個dfs搜尋樹，水藍色标記每個點的dfn（時間戳），梅紅色标記每個點的 low 值。
low 值宜從葉節點開始标記，因為其值作為子節點可以向上更新父節點的 low 值，比如序号為4的點有一條連向1号節點的返祖邊，其 low 值為1，7号結點 low 值等于其 dfn = 9，10号結點 low 值也為8，而對于8号結點，它的子樹中4号結點 low 值為1，根據 “ 如果 <u, v> 是搜尋樹的邊：low[u] = min(low[u], low[v]) ” ，其 low 值為1 ，再依次向上更新。
例如：10号點為割點，若将其去掉，其下的7号結點無法與上面的連通。
規律：【割點有兩類】：
- 子樹裡不存在跨越它連向它上方的點的邊
- 有多個兒子的根
(u, v)割邊（u 為父親，v 為兒子）：以 v 為根的子樹中不存在連向 u 以及 u 上方的邊。
用low和dfn的關系表示即注意割點的式子有等号，判割邊的沒有等号（如果有一條返祖邊将 v 與 u 相連，則dfn[u] = low[v] ，這時原本v和u相連的邊删掉也能連通，故u-v不是割邊）
- u點是割點， v 是 u 搜尋樹上的一個兒子：① dfn[u] <= low[v] —— v的子樹中沒有返祖邊能跨越 u 點；② 有多個兒子的根節點
- 邊是橋，搜尋樹上 v 是 u 的一個兒子：dfn[u] < low[v] —— v 的子樹中沒有返祖邊能跨越<u,v> 這條邊
“割點”代碼
注意第32行為 dfn[y]，與第25行的 low[y] 不一樣。在求“割邊”裡寫成 low[y] 雖然也不會錯，但在求割點裡就是錯的，可能有些題目資料不夠強這裡寫錯了也能過，但一旦錯了就很難找到，是以極度建議割點割邊代碼此處按照定義寫成一緻，能大大減少出錯率。
關于為什麼寫low[y]為錯的說明：
如下圖，因為搜尋的順序不确定（取決于建圖時的順序）若3号點的low值通過一條返祖邊更新為1後，再來更新5号結點時，若是 low[x] = min(low[x],low[y])，low[5]=low[3]=1，然後4号點就會繼承5号點的 low 值也為1，這樣dfn[3]>=low[4]，就會誤判點3不是割點，而事實上3号點是割點。這裡相當于是将1--3這條返祖邊與3--5這條返祖邊連起來當成了1--5的返祖邊，而我們的low值定義是目前點及其子樹通過一條返祖邊能連到的 最小dfn 值。5到3，3再到1，而3恰是我們的割點，而求割邊的時候就不會出現這種情況，跨越了一條邊就是跨越了一條邊，不會存在要兩條邊連在一起才跨越一條邊。
邊雙和點雙連通分量
- 把橋删了每個連通塊都是一個邊雙連通分量——标記處橋之後dfs一遍即可
- 點雙連通分量要複雜一些——一個割點可能屬于多個雙連通分量
dfs時（這裡假設在8号結點先搜向9的那條支鍊）……9入棧，6入棧，10入棧，再向上傳回（系統dfs遞歸調用的傳回，系統棧的10，6，9彈出，自己維護的棧沒有彈出）當傳回到結點8時，dfn[8] <= low[y]，判斷8為割點，此時彈出自己維護的棧裡8以上的所有結點（10，6，9）與8組成一個點雙連通分量；8再到7号結點，發現7号結點沒有兒子結點了，再傳回，又成立dfn[8]<=low[7]，8為割點，于是彈出7号點與8組成第二個點雙連通分量；8再到4，發現low[4]=1，low[4] < dfn[8]，8不是其中的割點……到最後回到根節點1，因為所有的結點的low值總不會比根節點的dfn還要小，即隻有一個子節點的根節點總是割點，是以靠1号根節點将剩餘的所有點彈出，組成最後一個點雙連通分量。（無所謂，根節點會出手）
邊雙連通分量 和 點雙連通分量 的縮點
- 每個邊雙連通分量縮成一個點，再用原來的橋把它們連起來
- 點雙連通分量因為一個割點可能包含在多個點雙連通分量裡面，是以我們将每個割點保留割點與其所在的點雙連通分量連邊即可。
如上圖的點雙連通分量可改為：
二、有向圖強連通分量
1.有向圖的弱連通與強連通
2.強連通分量
如上圖的黃色點構成一個強連通分量。
Kosaraju算法
對左圖，從1開始搜：1進棧，5進棧，8進棧，4進棧，3進棧，3不能往下搜了，3出棧，回到4，4也沒有向下搜的點，4出棧，回到8，6進棧，6出棧，8出棧，5出棧，1出棧；
然後再找圖中一個沒有通路過的點繼續上述操作，從2開始，2入棧，2出棧；
再從7開始，7入棧，9入棧，9出棧，7出棧。
得到出棧順序：3，4，6，8，5，1，2，9，7
再以這個出棧時間的逆序對反圖（即原來A->B變為B->A）進行dfs：從7開始，7無法到達其它點，7獨自為一個強連通分量；再看9，因為9原本能去到的7已經被删了，9也單獨是一個強連通分量；2号點為一個強連通分量；1号點為一個強連通分量（原本可以通向的2号點已經成為一個單獨的強連通分量了）；又5->3->4->8，3->6，是以5，3，4，6，8為一個強連通分量
原理：在一個 dfs 搜尋樹裡面，越先出棧說明越多的點可以到達這個點，即在它後面的點都能到達它，如【3，4，6，8，5，1】3後面的點都能到達3，4後面的點都能到達4，依此類推。若順序為A, B, C, 則實際圖中關系為 A<--B<--C，那麼倒叙，反圖能到（C-->B）也即原圖有反向邊能到（C<--B）【意會~意會~】
Tarjan 算法（求強連通分量）