[BOJ] 4803. 木.

[作成日]

2022-02-15

[分類]

dfs

ツリー

[問題リンク]

https://www.acmicpc.net/problem/4803

[要件]

の木が何本あるかを求めます.

[回答]
ツリーの重要な条件は、ループがあるかどうかです.まずグラフィック条件を満たし,cycleが発生しているかどうかを調べるだけでよい.cycleを生成するかどうかは、前のノードを除いて、次の移動するノードがすでにアクセスしている場合、cycleが生成されるため、dfsで簡単に解決できます.
[コード]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    static int N, M;
    static ArrayList<Integer>[] list;
    static boolean[] visited;
    static int cnt, step = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder resSb = new StringBuilder();

        while (true) {
            cnt = 0;
            step++;

            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());

            if (N == 0 && M == 0) {
                System.out.println(resSb);
                return;
            }

            // graph 생성
            list = new ArrayList[N + 1];
            visited = new boolean[N + 1];
            for (int i = 1; i <= N; i++) {
                list[i] = new ArrayList<>();
            }

            // graph 입력받기
            int a, b;
            for (int i = 0; i < M; i++) {
                st = new StringTokenizer(br.readLine());
                a = Integer.parseInt(st.nextToken());
                b = Integer.parseInt(st.nextToken());

                list[a].add(b);
                list[b].add(a);
            }

            for (int i = 1; i <= N; i++) {
                if (!visited[i]) {
                    // tree인 경우에만 cnt++
                    if (dfs(0, i)) cnt++;
                }
            }

            // print
            resSb.append(String.format("Case %d: ", step));
            if (cnt == 0) {
                resSb.append("No trees.\n");
            } else if (cnt == 1) {
                resSb.append("There is one tree.\n");
            } else {
                resSb.append(String.format("A forest of %d trees.\n", cnt));
            }
        }
    }

    public static boolean dfs(int before, int x) {
        // tree인지 검사하기 위해 바로 이전 것을 제외하고 이미 visited 한 것을 만나면 바로 false 반환
        for (int i = 0; i < list[x].size(); i++) {
            int next = list[x].get(i);

            if (next == before) continue;
            if (visited[next]) return false;
            visited[next] = true;
            if (!dfs(x, next)) return false;
        }
        return true;
    }
}

[感じ]
木の周期を判断する問題はよくあるので,もっと解くべきだ.