強連結成分分解について解説します
強連結とは、強連結成分とは
wikipediaより。
強連結
有向グラフが強連結であるとは、グラフ上の任意の2点間に有向路が存在することである。極大で強連結な部分グラフは、強連結成分という。
引用の通り、有向グラフにおいて、任意の2点間に有向路が存在（直接または別の頂点を通って行き来できる）するとグラフは強連結、また、グラフの部分グラフが強連結である場合は、それを強連結成分というようです。
強連結成分分解は、グラフを強連結成分に分解していくこと（そのままですが）となります。
例えば、このグラフは強連結です。
任意の2点間に有向路が存在（どの2点を選んでも直接または頂点を経由して移動することが可能）します。
そしてこのグラフには強連結成分が存在します。
四角で囲んでいる、グラフの部分グラフに該当する2箇所はそれぞれ強連結となっています。
強連結成分分解のやり方
手順は以下のとおりです。
- 適当な頂点からDFSして、帰りがけに頂点をラベリングする
- グラフを逆グラフ（辺の向きをすべて反転）にし、頂点ラベルの大きいものから再度DFSし、一度でたどり着けるところをそれぞれSCCとする。
こちらのリンクが参考になりましたので、引用させていただきます。
ここでは、とりあえずこの手順に従って実際の問題を解いて見ようと思います。
例題
E869120さんの、典型90問より、021 - Come Back in One Piece（★5）を解いてみました。典型的なSCCの問題のようです。
ACコードを載せておきます。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
public class Main {
// dfsで使用
static boolean[] checked = null;
// 辺
static ArrayList<ArrayList<Integer>> edge = null;
static ArrayList<ArrayList<Integer>> revEdge = null;
// 頂点のラベリング
static int count = 0;
static int[] vr = null;
// SCCのgroup番号
static int group[] = null;
static int groupNum = 0;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int v = sc.nextInt(); // 頂点数
int e = sc.nextInt(); // 辺数
edge = new ArrayList<>(); // 左要素→右要素が存在するかどうか
revEdge = new ArrayList<>(); // 左要素→右要素が存在するかどうか
vr = new int[v]; // 配列の添字がラベル、値が頂点
/*
* Listの初期化
*/
for (int i = 0; i < v; i++) {
edge.add(new ArrayList<>());
revEdge.add(new ArrayList<>());
}
/*
* 入力の受け取り、辺の格納
*/
for (int i = 0; i < e; i++) {
int s = sc.nextInt() - 1;
int t = sc.nextInt() - 1;
// 頂点sからtへの辺が存在
edge.get(s).add(t);
// 反転したグラフを考える際に使用
revEdge.get(t).add(s);
}
/*
* DFSして帰りがけに頂点をラベリング。
* 一度のDFSで終わらないことを加味し外側にもループ
*/
checked = new boolean[v]; // 探索した頂点を記録
for (int i = 0; i < v; i++) {
// i番目の頂点について探索
if (!checked[i]) {
firstDfs(i);
}
}
/*
* 再度DFSをラベルの大きい順・辺を逆転したグラフで行う。
* DFSが途切れるたびにgroupを更新
*/
Arrays.fill(checked, false); // 探索した頂点を記録
group = new int[v]; // 頂点vが属するグループ名
for (int i = v - 1; i >= 0; i--) {
// ラベリング大きい順から探索
int tansakuTyoten = vr[i];
if (!checked[tansakuTyoten]) {
secondDfs(tansakuTyoten, groupNum++);
}
}
long ans = 0;
for (int i : group) {
ans += (long) i * (i - 1) / 2l;
}
System.out.println(ans);
}
static void firstDfs(int now) {
// 頂点nowを受け取りdfs
checked[now] = true;
for (int i : edge.get(now)) {
if (!checked[i]) {
firstDfs(i);
}
}
// 引き返した際のラベル付け
vr[count++] = now;
}
static void secondDfs(int now, int groupNum) {
// 頂点nowを受け取りdfs
checked[now] = true;
group[groupNum]++;
for (int i : revEdge.get(now)) {
if (!checked[i]) {
secondDfs(i, groupNum);
}
}
}
}
なんとなく、DFSを2回やっていることを感じ取れると嬉しいです。
※変数名が問題と微妙に異なります。AOJの問題を先に解いていたのですがStackOverFlowErrorが出てしまい解けなかったのでこちらを例題としました。
問題はこちらです。Strongly Connected Components
再帰が多いからStackOverFlowErrorが出ているのだと思いますが、他のACコードも再帰使いまくっているのにこのコードだけStackOverFlowErrorが出る理由を突き止められず・・・。典型90問は解けたからいいか、、、という気持ちになっています。
ひとまず、強連結成分分解の実装についてはここまでとします。
※「競技プログラミング研究月間 - みんなでさらなる高みを目指そう」が開催中のようです。