関節点で訪れたノードのとき、どうしてdfs_lowではなくdfs_numを使うのか

Articulation pointsのアルゴリズムを勉強してるときに、訪れたノードの処理でどうしてdfs_numを使うのだろう。dfs_lowではダメなのかと思ったので、その解説記事です。

僕が問題を解くために書いたソースコードです。実装が正しいかを確かめるためにUVa 315を使いました。

実装方法に違いはあるかもしれませんが、訪れたノードの順番をdfs_numに。子ノードから訪れることができる最小の親ノードの順番をdfs_lowに保存しています。

public static void solve(int parent, int curr) {
    dfs_num[curr] = dfs_counter;
    dfs_low[curr] = dfs_counter;
    dfs_counter++;
    
    visited[curr] = 1;
    ArrayList<Integer> edges = map[curr];
    
    int numChildren = 0;
    
    for (int i = 0; i < edges.size(); i++) {
        int next = edges.get(i);
        
        if (next == parent) continue;
        
        if (visited[next] == 1) {
            dfs_low[curr] = Math.min(dfs_low[curr], dfs_num[next]); 
         // 疑問なのはここ。どうして、dfs_low[next]は使えないのだろう?
        } else {
            numChildren++;
            solve(curr, next);
            
            dfs_low[curr] = Math.min(dfs_low[curr], dfs_low[next]);
            
            if (parent == -1 && numChildren > 1) {
                isArticulation[curr] = 1;
            }
            if (parent != -1 && dfs_num[curr] <= dfs_low[next]) {
                isArticulation[curr] = 1;
            }
        }
    }
}

この実装方法ではWrong Answerをもらいます。どこがダメなのかを探るためにudebugを使いました。ほとんどのテストケースはパスするのですが、ある一定の条件のテストだけパスできませんでした。それは、こんなグラフの場合です。

f:id:ilovehugeworld:20170309122207p:plain

こういったテストケースの場合、dfs_numを使わないと正しい答えがでません。例えば「5」にいる場合でnextが3の場合、「3」はすでに訪れてるので、訪れてるときの処理が実行されます。このとき、「3」から「1」へのチェックがすでに行われてるとしたらどうでしょう?データの保存の仕方によっては有りえる話です。「1」のdfs_lowの値は、「3」のdfs_lowの値より小さいため「3」のdfs_lowの値は「1」のdfs_lowの値に書き換えられています。

その状態でMath.minが呼ばれるので「5」のdfs_lowは「1」の順番を保持することになります。dfs_lowは子ノードから訪れることができる最小の親ノードの順番を保存するため、これは正しくありません。つまり、dfs_lowを使うと2つ上の親ノードの順番を保存するケースが有るということです。この状態で子ノードのdfs_lowと今いるノードのdfs_numを比べるため、正しい比較ができません。そのためバグが生まれます。

以下にUVa 315と同じフォーマットで上記のテストケースを置いておくため、気になる方は実際に確かめてください。

5
1 2 3
2 1 3
3 1 2 4 5
4 3 5
5 4 3
0