[BOJ 4803, Java] Tree

Problem Link

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

)

Categories

Data Structures, Depth-First Search (DFS), Disjoint Sets, Graph Theory, Graph Traversal, Trees

Description

This problem involved counting the number of trees using tree properties. It can be solved by excluding cycles from the set of connected elements.

1. Check if every node has been visited
2. Perform depth-first search while adding unvisited nodes to the tree
3. If a cycle is formed, mark all nodes in the cycle as visited
4. If no cycle is formed, the set is a tree, so count it as 1

I implemented the logic described above. After much deliberation on how to handle the counting during depth-first search, I wrote the following code:

    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;

    }

I wrote the code to start from the root node and perform a recursive search; if a cycle is encountered, it traverses all nodes and returns 0.

If no cycle is found, the traversal completes normally and returns 1. By continuously counting these return values, we can determine the number of trees!

Solution Code

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();

    }

}