[백준 Gold 4] 4803 트리 - Java

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

4803번: 트리

 

 

접근 과정 : 

• 사이클이 형성되지 않은 트리만을 찾아서 갯수를 세주면 된다.
• 간선이 연결될 때, 만약 두 정점중 하나가 사이클에 포함되어 있거나, 해당 간선으로 사이클을 형성하게 되는 경우를 확인해야 한다.
• 트리의 루트 노드를 기억하고, 이를 이용해서 사이클을 확인했다.
• A,B를 잇는 간선이 있을 때, roo[A] == root[B] 라면 이는 사이클을 형성하게 된다.
• root[A] 혹은 root[B]가 이미 사이클이라면 이 역시 둘 모두 사이클을 형성하는 관계가 된다.

 

소스 코드 및 결과 :

package BOJ;

/* 
    트리
*/

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

public class BOJ4803 {

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

     
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        int T = 1;

        while (true) {
            st = new StringTokenizer(br.readLine());

            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());

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

            tree = new int[n + 1];
            for (int i = 1; i <= n; i++) {
                tree[i] = i;
            }

            while (m-- > 0) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());

                a = findTree(a);
                b = findTree(b);

                if (a > b) {
                    union(b, a);
                } else {
                    union(a, b);
                }
            }

            int count = 0;
            for (int i = 1; i <= n; i++) {

                int x = findTree(i);

                if (tree[x] == i) {
                    count++;
                }
            }

            sb.append("Case ").append(T++);
            switch (count) {
                case 0:
                    sb.append(": No trees.\n");
                    break;

                case 1:
                    sb.append(": There is one tree.\n");
                    break;
                default:
                    sb.append(": A forest of ").append(count).append(" trees.\n");
                    break;
            }

        }
        System.out.println(sb.toString().trim());
    }

    static int[] tree;

    static int findTree(int x) {
        if (tree[x] == x) {
            return x;
        }

        return tree[x] = findTree(tree[x]);
    }

    static void union(int a, int b) {

        if (a == b) {
            tree[a] = 0;
            return;
        }

        tree[b] = a;

    }
}

 

P.S 

실수를 주의하자!!!

사이클의 존재를 잊거나,, 테스크 케이스 숫자++을 잊거나, 결과 문자열 실수를 하지 않도록!!!

난 3가지 실수를 다 했다....