強連結成分分解SCC-Tarjanアルゴリズム
投稿日： 更新日:
Tarjanアルゴリズム
１回のDFSで強連結成分を識別するアルゴリズムです。
有向グラフにおいて、頂点集合を考える
が強連結であるとは、集合内の全ての頂点が互いに行き来可能であること。
が強連結成分であるとは、が強連結でありかつ、に以外の頂点を追加すると強連結ではなくなる。
アルゴリズムの動作
- 各頂点の訪問順序
ordと低リンク値low、所属する強連結成分の番号group、スタックを用意します - 未訪問の頂点
vからDFSを開始する - DFSで訪れた頂点
vに対し以下の操作を行う。ord[v]とlow[v]を現在の訪問順序で初期化する- ノード
vをスタックにプッシュする - ノード
vから到達可能な頂点nxtについて以下の処理を行うnxtが未訪問の場合再帰的にDFSを行い、low[v]を更新するnxtが訪問済みかつまだ強連結成分に割り当てられていない場合low[v]をord[nxt]の最小値で更新する
ord[v]とlow[v]が一致する場合、vを強連結成分の代表頂点と識別し以下の処理を行う- スタックから頂点を取り出し、強連結成分に割り当てる
- ノード
vが取り出されるまで続ける - 強連結成分の数をインクリメントする
- 強連結成分の情報を返す
低リンク値：DFS木の辺、後退辺または交差辺を使って到達出来るノードの最小の訪問順序
メモ
low[v]は後退辺または交差辺を返して到達出来る頂点の最小のordを記録している。
vが連結成分の根でない場合、low[v] < ord[v]が成立する。vが根でない場合、vから後退辺もしくは交差辺を用いてDFS木を遡ることが出来る。遡って到達出来る頂点はord[v]よりも必ず小さくなる。そのため、low[v] < ord[v]が成立する。
low[v] == ord[v]が成立する場合、vは強連結成分の根である。なぜなら、後退辺、交差辺を使ってvから根に向かって遡ることが出来ないことを示しているからである。
実装
C++での実装です
以下のコードはCC0-1.0ライセンスです
vector<int> scc(const vector<vector<int>>& to){
const int n = to.size();
vector<int> ord(n, -1), low(n);
vector<int> group(n, -1);
int group_num = 0;
int now_ord = 0;
vector<int> st;
st.reserve(n);
auto dfs = [&](auto& self, int v)->void{
low[v] = ord[v] = now_ord;
++now_ord;
st.push_back(v);
for(int nxt: to[v]){
if(ord[nxt] == -1){
self(self, nxt);
low[v] = min(low[v], low[nxt]);
}else if(group[nxt] == -1){
low[v] = min(low[v], ord[nxt]);
}
}
if(ord[v] == low[v]){
while(true){
int u = st.back();
st.pop_back();
group[u] = group_num;
if(v == u)break;
}
++group_num;
}
};
for(int i = 0;i < n; ++i){
if(ord[i] == -1){
dfs(dfs, i);
}
}
return group;
}
verify1: https://judge.yosupo.jp/problem/scc