AtCoder Regular Contest 037 B問題 バウムテストをJavaで解いてみてハマったこと

空き時間にQiitaで競技プログラミングの記事を読みながら勉強を進めています。今回はAtCoder 版！蟻本 (初級編) にある深さ優先探索の問題のひとつを解いた話を書きます。

qiita.com

問題

以下の問題です。ノードとエッジ情報が与えられ、閉路を持たない連結成分の個数を求める問題です。

arc037.contest.atcoder.jp

方針

下図のように深さ優先探索をして閉路を探して行きます。

深さ優先探索

閉路の条件はノードがすでに訪れたものであるかどうか。私は未訪問ノードを記憶しましたが、空リストに訪問ノードを記憶していくやりかたも考えられます。

判定条件

正解コード

import java.util.*;
import java.awt.Point;
class Main {
    static ArrayList<Integer> unVisitList;
    static Point[] edges;
    public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int M = sc.nextInt();
    unVisitList = new ArrayList<Integer>();
    edges = new Point[M];
    for(int i = 0; i < N; i++) {
        unVisitList.add(i+1);
    }
    for(int i = 0; i < M; i++) {
        edges[i] = new Point(sc.nextInt(), sc.nextInt());
    }
    int cnt = 0;
    while(unVisitList.size() != 0) {
        boolean isTrue = searchTree(unVisitList.get(0));
        if(isTrue) cnt++;
    }
    System.out.println(cnt);
    }

    // エッジを辿って下位ノードを検索する
    public static int nextNode(int n) {
    for(int i = 0; i < edges.length; i++) {
        if(edges[i].getX() == n){
        int num = (int)(edges[i].getY());
        edges[i].move(-1,-1); // エッジは使ったものは(-1,-1)を入れて消していく
        return num;
        }
        else if(edges[i].getY() == n) {
        int num = (int)(edges[i].getX());
        edges[i].move(-1,-1);
        return num;
        }
    }
    return -1;
    }

    // ノードがunvisitかどうか調べ、さらに下位ノードを探索する（再起）
    public static boolean searchTree(int i) {
        
        // ノードiがunVisitかどうかを調べる
    if(unVisitList.contains((Integer)(i))) {
        unVisitList.remove((Integer)(i));
    }else {
        return false; // unVisitでなければ閉路なので、木構造ではないためfalseを返す
    }
    int nextNode;
    boolean isTree = true;
    while((nextNode = nextNode(i)) > 0) {
        boolean isNext = searchTree(nextNode);
        isTree = isTree && isNext;
    }
    return isTree;
    }
}

ハマったところ

searchTree関数の中で再起するときに、正解コードは

boolean isTree = true;
while((nextNode = nextNode(i)) > 0) {
    boolean isNext = searchTree(nextNode);
    isTree = isTree && isNext;
}

としていますが、以下のように一行で書くと関数が呼び出されず誤作動します。

boolean isTree = true;
while((nextNode = nextNode(i)) > 0) {
    isTree = isTree && searchTree(nextNode);
}

isTreeがfalseだとわかっている場合は関数が呼び出されていいないようです。ちなみにsearchTree(nextNode) && isTree の順番だと正常に動きます。 誤作動するテストケースとしては、

4 4
1 4
2 4
3 4
2 1

がありました。深さ優先探索で、1->4->2->1->4->3の順に閉路があるかどうか探索しますが、1->4->2->1で閉路を見つけたあと、isTreeがfalseになり、4->3を調べるためのsearchTreeは呼び出されないので、3がunVisitにならずに別の木としてカウントされてしまいます。 サイトのテストは全て通ったので気づくのに時間がかかりました。

感想

複合代入演算子"&="はあまり使ったことがなく、こんなハマりポイントがあったとはという感じでした。