BOJ. Tree (4803)

Approach

A tree is a connected, acyclic undirected graph. For each unvisited vertex, run a breadth-first traversal to visit its entire connected component. Mark each vertex visited when it is enqueued so that no vertex is queued more than once. While traversing an edge, the neighbor is a cycle witness if it has already been visited and is not the current vertex’s parent; the parent edge itself is the one edge that must be ignored in an undirected graph. Count the component only if no cycle was found. This also counts an isolated vertex as a tree.

The traversal examines every vertex and adjacency entry a constant number of times, so the running time is O(V + E) and the graph plus visited/queue storage uses O(V + E) space.

Problem link

Java

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

public class Main {
    public static void main(String[] args) throws IOException {
        FastScanner input = new FastScanner();
        StringBuilder output = new StringBuilder();
        int caseNumber = 1;

        while (true) {
            int vertexCount = input.nextInt();
            int edgeCount = input.nextInt();
            if (vertexCount == 0 && edgeCount == 0) {
                break;
            }

            @SuppressWarnings("unchecked")
            ArrayList<Integer>[] graph = new ArrayList[vertexCount];
            for (int vertex = 0; vertex < vertexCount; vertex++) {
                graph[vertex] = new ArrayList<>();
            }

            for (int edge = 0; edge < edgeCount; edge++) {
                int first = input.nextInt() - 1;
                int second = input.nextInt() - 1;
                graph[first].add(second);
                graph[second].add(first);
            }

            boolean[] visited = new boolean[vertexCount];
            int[] parent = new int[vertexCount];
            java.util.Arrays.fill(parent, -1);
            int treeCount = 0;
            for (int start = 0; start < vertexCount; start++) {
                if (visited[start]) {
                    continue;
                }

                visited[start] = true;
                Queue<Integer> queue = new ArrayDeque<>();
                queue.add(start);
                boolean hasCycle = false;

                while (!queue.isEmpty()) {
                    int current = queue.remove();
                    for (int neighbor : graph[current]) {
                        if (!visited[neighbor]) {
                            visited[neighbor] = true;
                            parent[neighbor] = current;
                            queue.add(neighbor);
                        } else if (neighbor != parent[current]) {
                            hasCycle = true;
                        }
                    }
                }

                if (!hasCycle) {
                    treeCount++;
                }
            }

            if (treeCount == 0) {
                output.append("Case ").append(caseNumber).append(": No trees.\n");
            } else if (treeCount == 1) {
                output.append("Case ").append(caseNumber).append(": There is one tree.\n");
            } else {
                output.append("Case ").append(caseNumber).append(": A forest of ")
                        .append(treeCount).append(" trees.\n");
            }
            caseNumber++;
        }

        System.out.print(output);
    }

    private static class FastScanner {
        private final BufferedReader reader = new BufferedReader(
                new InputStreamReader(System.in));
        private StringTokenizer tokenizer;

        String next() throws IOException {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                tokenizer = new StringTokenizer(reader.readLine());
            }
            return tokenizer.nextToken();
        }

        int nextInt() throws IOException {
            return Integer.parseInt(next());
        }
    }
}