(畫圖什麼真辛苦)
強連通分量:
![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLiQ3chVEa0V3bT9CX5RXa2Fmcn9CXwczLcVmds92czlGZvwVP9EUTDZ0aRJkSwk0LcxGbpZ2LcBDM08CXlpXazRnbvZ2LcRlMMVDT2EWNvwFdu9mZvwVPF12YoJ1VZRXOWlVe5ckW1Z0RjZXUYpVd1kmYr50MZV3YyI2cKJDT29GRjBjUIF2LcRHelR3LcJzLctmch1mclRXY39DOxcjNzEjMzEjNwYDM0EDMy8CX0Vmbu4GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.jpg)
在有向圖 G 中,若兩個頂點互相可達,則稱兩個頂點強連通(strongly
connected)。如果有向圖G的每兩個頂點都強連通,稱G是一個強連通圖。非強連通圖有向圖的極大強連通子圖,稱為強連通分量(strongly
connected components)。比如上面這幅圖(
a, b, e ), ( d, c, h ), ( f, g ) 分别為三個 SCC。
tarjan算法僞代碼:
該算法由 Robert
Tarjan 發明,原論文:
時間複雜度是深搜的時間複雜度 O( N
+ E )。
tarjan算法的執行動态圖:
1.建圖,每個頂點有三個域,第一個是頂點名,第二個空格是發現該點的時間戳 DFN ,第三個空格是該點能夠追溯到的最早的棧中節點的次序号
LOW。
2. 深搜,比如搜尋路徑為 a --> b --> c --> g --> f, 沿途記下自身的 DFN 和 LOW
3.達到 f 點後,f 點隻有一個可達頂點 g, 但 g 不是 f 的後繼頂點,且 g 在棧中,則更新 f 的 LOW 變為 g 的發現時間。
4.這時候回到 g 點,但是 f 點還得再棧中,隻有發現時間 DFN 與 LOW 相同的頂點才能從棧中彈出(和壓在上面的節點一起彈出構成SCC)
5.這時候 g 點的 DFN == LOW
6.于是将 f 和 g 都彈出
7.如虛線所示,他們構成了一個SCC
8.下面就是一樣的了,( 圖畫的好辛苦 )
=========================================================================================
========================================================================================
==========================================================================================
python代碼:
運作結果:
C++代碼: