<style type="text/css"> .slides { text-align: left !important; } </style> # 強連通分量 #### Author:H1de_on_bruH ---- ## 概要 定義 Tarjan演算法 Kosaraju's演算法 --- ### 給定一個有向圖 求有幾個強連通分量 強連通分量(簡稱SCC:Strongly Connected Components)的意思是: **這個子圖裡面任意兩點都可以找到路互通**  ---- ### 怎麼做? 直接照定義去爆搜複雜度會達到$O(N^2+M)$ 這看起來非常不健康 --- ### 想法1: 試著把這個有向圖想像成一棵有向樹 接者呢? ~~破梗囉~~ ---- ### Tarjan演算法 ----  考慮這個圖 我們可以看到有兩個比較特殊的邊 $3 \rightarrow1$跟$4\rightarrow3$ ---- 藍色那條我們稱為返祖邊 表示從這個邊可以返回該節點的祖先 紅色的叫橫插邊 表示可以尋訪到之前尋訪過的節點 還有另外一種叫做前向邊 表示會尋訪到自己之前就尋訪過的節點 也就是返祖邊反過來 ---- 我們考慮這個跟SCC的關係 如果節點$u$是某個SCC在DFS時遇到的第一個節點 那這個SCC其餘的點都必在以$u$為根的搜索樹子樹中 我們稱$u$為這個SCC的根 :::spoiler 反證法 假設有個節點$v$在這個SCC裡面卻不在$u$的子樹中 那$u$到$v$的路徑中必定有一條離開子樹的邊 這樣只有可能是返祖邊或是橫插邊 然而這兩種邊所指向的節點必是已經被尋訪過的 這就跟$u$是這個SCC的根矛盾 故得證# ::: ---- #### Tarjan實現 在每個節點維護下列幾個值 * $dfn_i$:DFS時節點$i$被搜到的編號 * $low_i$:定義為其子樹以下節點的$dfn$最小值 ---- 做DFS時 若在$u$點時有邊指向$v$ 則考慮下列三種狀況 * $v$未被尋訪過:對他尋訪下去後回溯時用$low_v$去更新$low_u$ * $v$被訪問過 且在stack中:即表示$v$為$u$之祖先節點 利用$dfn_v$更新$low_u$ * $v$被訪問過 且不在stack中:表示$v$所在之SCC已被處理 不做任何更新 [sample code](https://pastebin.com/SAxTYWVH) --- ### 想法2: 走得過去也走得回來 :thinking_face: 那做兩次DFS是不是就可以了? ~~又 破梗囉~~ ---- ### Kosaraju's演算法 aka 兩次DFS ---- 同樣的圖 我們考慮它正反圖的關係   ---- 若拿在原圖時的一個SCC 若點$u$為第一次DFS時該SCC中最後一個遍歷到的 那點$u$必可以做這個SCC在反圖的根 ---- #### 實作 我們先用DFS遍歷原圖一次 並記錄下各個點的順序 之後再把這個順序倒過來 依照這個倒過來的順序去DFS ```cpp= for(int i=1;i<=n;i++)if(vis[i]==0)dfs1(i); reverse(ts.begin(),ts.end());//ts代表剛剛dfs1走過的順序 for(auto i:ts)if(vis[i])dfs2(i); ``` ---- 完整版請參考下方連結 [sample code](https://pastebin.com/nDcPpDxi) --- ### 例題 [CF:427C](https://codeforces.com/contest/427/problem/C) 裸到吐的裸題 [CSES:Giant pizza](https://cses.fi/problemset/task/1684/) ~~噁心實作，P_L超噁~~:face_vomiting: ---- 比起Tarjan Kosaraju的泛用性比較低 只能拿來求SCC(Tarjan還可以求割點跟橋) 複雜度上來講Tarjan常數也比較小 不過Kosaraju的實作簡單 有能力的話建議都多熟悉 ---- # {謝謝各位的聽講|夕張超可愛的對吧}