자바 - 백준 4803 / 트리

풀이 방법

틀린 방식

1. 유니온 파인드를 통해 사이클 발생 여부 판단
2. 사이클 발생시 → 트리 없음 기록
3. 사이클 미 발생시, parent 배열을 통해 루트 노드 개수 카운팅

틀린 이유

1. 사이클 발생 시, 해당 그래프만 트리가 아니고, 다른 그래프는 트리일 가능성 존재
2. parent 배열이 최신 상태로 업데이트 되지 않은 경우, 루트 노드가 아닐 가능성이 존재한다.

해결 방법

1. 사이클 발생 시 → 사이클 발생 노드 기록
2. 루트 노드를 parent 배열 말고, find()를 통해 찾기

맞는 풀이

1. 유니온 파인드를 통해 사이클 발생 여부 판단
   1. 사이클 발생시, 해당 노드에 사이클이라고 표시
   2. 사이클 미 발생시, 루트 노드가 사이클인지 아닌지를 자식 노드 둘로 판단
      1. 자식 노드 둘다 사이클이 아니라면 루트 노드도 사이클 아님
2. find()를 통해 노드들의 루트 노드가 사이클인지 판단 후 카운팅

코드

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

/**
* 백준 4803
* 트리
* 골드4
* <https://www.acmicpc.net/problem/4803>
*/
public class Boj4803 {

    private static int n;
    private static int m;
    private static int[] parent;
    private static boolean[] isTree;

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

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

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

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

            parent = new int[n];
            for(int i = 0; i < n; i++)
                parent[i] = i;

            isTree = new boolean[n];
            Arrays.fill(isTree, true);

            for(int i = 0; i < m; i++) {
                st = new StringTokenizer(br.readLine());

                int a = Integer.parseInt(st.nextToken()) - 1;
                int b = Integer.parseInt(st.nextToken()) - 1;

                hasCycle(a, b);
            }

            int answer = countingTree();

            if(answer == 0)
                sb.append("Case ").append(index).append(": ").append("No trees.").append("\\n");
            else if(answer == 1)
                sb.append("Case ").append(index).append(": ").append("There is one tree.").append("\\n");
            else
                sb.append("Case ").append(index).append(": ").append("A forest of ").append(answer).append(" trees.").append("\\n");

            index++;
        }

        System.out.print(sb);
    }

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

        if(a == b) {
            isTree[a] = false;
        }

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

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

        return parent[a] = find(parent[a]);
    }

    private static int countingTree() {
        Set s = new HashSet<>();

        for(int i = 0; i < n; i++) {
            int root = find(i);

            if(isTree[root])
                s.add(root);
        }

        return s.size();
    }
}