読者です 読者をやめる 読者になる 読者になる

強連結成分分解においてどうしてスタックにあることを確かめる必要があるのか

強連結成分分解(SCC)を発見するTarjanアルゴリズムを学んでいたのですが、どうしてスタックにあるかどうかを確認する必要があるかがわからなかったのでその答えです。

答えを確かめるためにUVa 247を使いました。僕が解くために書いたソースコードは以下のとおりです。関節点で書いた記事と同じで、訪れたノードの順番をdfs_numに。子ノードから訪れることができる最小の親ノードの順番をdfs_lowに保存しています。

public static int[] dfs_num;
public static int[] dfs_low;
public static Stack<Integer> stack;
public static int[] inStack;
public static int dfs_counter;

public static void main(String[] args) {
  
  // Graphを隣接リストとして取得。変数名はadjList

  for (int i = 0; i < adjList.length; i++) {
    if (dfs_num[i] == 0) {
      solve(i);
    }
  }
}

public static void solve(int curr) {
  dfs_num[curr] = dfs_counter;
  dfs_low[curr] = dfs_counter;
  dfs_counter++;

  stack.push(curr);
  inStack[curr] = 1;
  ArrayList<Integer> edge = adjList[curr];

  for (int i = 0; i < edge.size(); i++) {
    int next = edge.get(i);
  
    if (dfs_num[next] == 0) {
      solve(next);
    }
    if (inStack[next] == 1) { // どうしてここのチェックが必要なのかがわからない。
      dfs_low[curr] = Math.min(dfs_low[curr], dfs_low[next]);
    }
  }

  if (dfs_num[curr] == dfs_low[curr]) {
    int pop = stack.pop();
    System.out.printf("SCC: (");
    while (pop != curr) {
      System.out.printf("%d ", pop);
      inStack[pop] = 0;
      pop = stack.pop();
    } 
    inStack[pop] = 0;
    System.out.printf("%d)\n", pop);
  }
}

どうして、スタックにあることを確かめる必要があるかはこういうテストケースを考えると理解できます。

f:id:ilovehugeworld:20170315101455p:plain

solveを呼ぶforループは0から始まるので、最初はノード0をチェックします。ノード0からいけるノードはないので再帰的にsolveを呼ぶことなく終了し、SCC (0)をプリントします。次にsolve(1)が呼ばれます。今回はエッジがあるのでforループに入り、問題のif文に来ます。もし、ここでif (inStack[next] == 1)がなければそのままノード0のdfs_low[0]の1を取得しdfs_low[1]に入れてしまいます。

そうすると、forループ後のdfs_num[curr] == dfs_low[curr]がtrueではなくなるため、SCC (1)をプリントしません。つもりこのif文は、今調べてるノードのdfs_low値を、すでに強連結されてるノードのdfs_lowで上書きしないためのif文だったのです。

逆にいうとnextが今調べてるノードと強連結する可能性がある時だけdfs_low[curr]をアップデートするという感じでしょうか。どうもわかりやすくできないかなと思ったのですが、何も思いつきませんでした。自分がきちんと実装できてるかを確かめるためにUVa 247を解いてみるといいかもしれません。