[백준 4803] 트리(Java)

문제 링크 : https://www.acmicpc.net/problem/4803

이 문제는 유니온 파인드를 이용하여 풀 수 있습니다. 문제에서 구하고자 하는 부분은 트리의 개수를 세는 것입니다. 즉, 유니온 파인드를 이용하여 간선 정보를 통해 노드끼리 연결해준 후, 서로 다른 부모 노드의 개수를 세주면 됩니다.

하지만 주의할 점은 사이클은 포함시키지 않는 것입니다. 따라서 유니온 코드를 기존 방식에서 몇 가지 추가가 필요합니다.

유니온 코드의 경우 파인드 코드를 통해 두 노드의 부모 노드를 탐색한 후 이들이 다르다면 한 쪽의 노드로 합치는 작업을 수행합니다. 그럼 만약 두 노드가 같다면 무슨 의미일까요? 바로 두 노드가 같은 경우는 이미 방문한 노드를 다시 한 번 방문했다라고 볼 수 있습니다. 즉, 사이클이 성립되는 것입니다. 따라서 두 노드가 같을 경우 기존 유니온 작업을 진행한 후 다른 한쪽을 0으로 처리하여 방문했다는 표시를 줍니다. 이후 Set을 이용하여 중복되는 부모 노드를 체크하면서, 부모 배열을 탐색하여 0이 아닌 노드를 Set에 추가하여 그 크기를 리턴합니다.

다음은 코드입니다.

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

class Main{
    static int[] parent;


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

        while(true){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            if(n==0 && m==0) break;

            sb.append("Case "+(cnt++)+": ");
            parent = new int[n+1];
            for(int i=1;i<=n;i++) parent[i] = i;

            for(int i=0;i<m;i++){
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                union(a,b);
            }

            Set<Integer> tree = new HashSet<>();
            for(int i=1;i<=n;i++){
                if(find(parent[i])>0) tree.add(find(parent[i]));
            }

            if(tree.size()==0) sb.append("No trees.");
            else if(tree.size()==1) sb.append("There is one tree.");
            else sb.append("A forest of "+tree.size()+" trees.");
            sb.append("\n");
        }

        System.out.println(sb);
    }

    static void union(int a, int b){
        a = find(a);
        b = find(b);

        if(a==b){
            parent[b] = a;
            parent[a] = 0;
        }
        else if(a<b) parent[b] = a;
        else parent[a] = b;
    }

    static int find(int a){
        if(a == parent[a]) return a;
        else return parent[a] = find(parent[a]);
    }
}