백준 4803 - 트리

문제

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

리뷰

유니온 파인드를 이용하여 풀이할 수 있는 문제였다.

트리의 조건을 충족하기 위해선 사이클이 존재하지 않아야 되는데
parent 를 $2 \times (N+1)$ 의 2차원 배열로 설정하고 parent[0] 에 해당 정점이
포함된 집합의 사이클 존재 여부를 기록하도록 설정하였다.

이 조건을 충족하기 위해 입력으로 들어오는 두 정점을 같은 집합으로 형성하고
이미 같은 집합내에 속한 두 정점이 연결 관계로 들어올 경우 사이클이 존재하는 것으로
판단하여 루트와 자식 노드 모두의 사이클 존재 여부를 기록한다. (parent[0]=1)
이후 루트를 기준으로 사이클이 존재하지 않는 것만 탐색하여 카운팅해주면 된다.

로직의 시간복잡도는 유니온 파인드의 $O(a(N))$에 연결 관계의 수인 $M$이 곱해진
$O(Ma(N))$의 형태로 수렴하고 이는 최대 연산의 경우에도 제한 조건인 1초를 무난히
통과한다.

코드

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

import static java.lang.Integer.*;

public class Main {
    static int[][] parent;

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

        while (true) {
            st = new StringTokenizer(br.readLine());
            int n = parseInt(st.nextToken());
            int m = parseInt(st.nextToken());

            if (n == 0 && m == 0) break;

            parent = new int[2][n + 1];
            Arrays.fill(parent[1], -1);

            while (m-- > 0) { // O(M a(N))
                st = new StringTokenizer(br.readLine());
                int u = parseInt(st.nextToken());
                int v = parseInt(st.nextToken());

                int r1 = find(u);
                int r2 = find(v);

                if (r1 == r2) { // O(a(N))
                    parent[0][r1] = 1;
                } else {
                    if (parent[1][r1] < parent[1][r2]) {
                        parent[1][r1] += parent[1][r2];
                        parent[1][r2] = r1;

                        if (parent[0][r2] == 1)
                            parent[0][r1] = 1;

                    } else {
                        parent[1][r2] += parent[1][r1];
                        parent[1][r1] = r2;

                        if (parent[0][r1] == 1)
                            parent[0][r2] = 1;
                    }
                }
            }

            int result = 0;
            for (int i = 1; i < parent[1].length; i++)
                if (parent[0][i] == 0 && parent[1][i] < 0)
                    result++;

            sb.append("Case " + phase + ": ");

            switch (result) {
                case 0:
                    sb.append("No trees.\n");
                    break;
                case 1:
                    sb.append("There is one tree.\n");
                    break;
                default:
                    sb.append("A forest of " + result + " trees.\n");
            }

            phase++;
        }

        System.out.print(sb);
        br.close();
    }

    static int find(int u) {
        if (parent[1][u] < 0) return u;

        return parent[1][u] = find(parent[1][u]);
    }
}

결과