[BOJ 4803, Java] 木

問題リンク

[BOJ 4803](https://www.acmicpc.net/problem/4803

)

カテゴリ

データ構造(data_structures)、深さ優先探索(dfs)、分離集合(disjoint_set)、グラフ理論(graphs)、グラフ探索(graph_traversal)、木(trees)

説明

木の性質を利用して、木の数をカウントする問題だった。この問題では、連結要素で構成されたものの中からサイクルを除外することで解決できる。

1. すべてのノードについて訪問確認
2. 未訪問の点について、木に組み込みながら深さ優先探索
3. サイクルを形成している場合、構成しているすべての点を訪問済みとして処理
4. サイクルを形成していない場合、その集合は木であるため1をカウント

上記のようなロジックで実装し、深さ優先探索を行いながらカウント処理をどうするか悩んだ結果、以下のコードを作成した。

    public static int dfs(int nowNode, int parent, boolean[] visitLog, HashMap<Integer, ArrayList<Integer>> graph) {

        for (int nextNode : graph.get(nowNode)) {

            if (nextNode != parent && !visitLog[nextNode]) {

                visitLog[nextNode] = true;

                int result = dfs(nextNode, nowNode, visitLog, graph);
                if (result == 0) {
                    return 0;
                }

            } else if (nextNode != parent && visitLog[nextNode]) {
                return 0;
            }

        }

        return 1;

    }

最初の点から再帰的に訪問処理を行いながら探索し、サイクルが見つかった場合は基本的にすべての点を巡回した後、0を返す構造で作成した。

もしサイクルが現れなかった場合は、正常に巡回を終えて1を返すため、その関数の戻り値をカウントし続けることで、木の数を把握できる！

解答コード

import java.io.*;
import java.util.*;

public class Main {

    public static int dfs(int nowNode, int parent, boolean[] visitLog, HashMap<Integer, ArrayList<Integer>> graph) {

        for (int nextNode : graph.get(nowNode)) {

            if (nextNode != parent && !visitLog[nextNode]) {

                visitLog[nextNode] = true;

                int result = dfs(nextNode, nowNode, visitLog, graph);
                if (result == 0) {
                    return 0;
                }

            } else if (nextNode != parent && visitLog[nextNode]) {
                return 0;
            }

        }

        return 1;

    }

    public static void main(String[] args) throws IOException {

        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter output = new BufferedWriter(new OutputStreamWriter(System.out));

        int testCase = 0;

        ArrayList<String> outputArr = new ArrayList<>();

        while (true) {

            StringTokenizer treeInfo = new StringTokenizer(input.readLine(), "[ ]");
            int nodeNumber = Integer.parseInt(treeInfo.nextToken());
            int edgeNumber = Integer.parseInt(treeInfo.nextToken());

            if (nodeNumber == 0 && edgeNumber == 0) {
                break;
            }

            testCase += 1;

            int treeCount = 0;
            boolean[] isVisited = new boolean[nodeNumber + 1];

            StringBuilder stringBuilder = new StringBuilder();
            stringBuilder.append("Case ");
            stringBuilder.append(testCase);
            stringBuilder.append(": ");

            HashMap<Integer, ArrayList<Integer>> treeGraph = new HashMap<>();
            for (int i = 1; i < nodeNumber + 1; i++) {
                treeGraph.put(i, new ArrayList<>());
            }

            for (int i = 0; i < edgeNumber; i++) {

                StringTokenizer edgeInfo = new StringTokenizer(input.readLine(), "[ ]");
                int startNode = Integer.parseInt(edgeInfo.nextToken());
                int endNode = Integer.parseInt(edgeInfo.nextToken());

                treeGraph.get(startNode).add(endNode);
                treeGraph.get(endNode).add(startNode);

            }

            for (int i = 1; i < nodeNumber + 1; i++) {

                isVisited[i] = true;
                treeCount += dfs(i, 0, isVisited, treeGraph);
            }

            if (treeCount == 0) {
                stringBuilder.append("No trees.");
            } else if (treeCount == 1) {
                stringBuilder.append("There is one tree.");
            } else if (treeCount > 1) {
                stringBuilder.append("A forest of ");
                stringBuilder.append(treeCount);
                stringBuilder.append(" trees.");
            }

            outputArr.add(stringBuilder.toString());

        }

        for (int i = 0; i < testCase; i++) {

            if (i != testCase - 1) {
                output.write(outputArr.get(i) + "\n");
            } else {
                output.write(outputArr.get(i));
            }

        }

        output.flush();
        output.close();

    }

}