[백준] 4803번 - 트리 (Gold 4)

문제 링크

[백준] 4803번 - 트리 (Gold 4)

문제 설명

각 그래프의 정점의 개수와 간선의 개수 및 정보가 주어진다.
각각의 그래프가 몇 개의 트리로 구성되어 있는지를 출력한다.
만일 트리가 한개도 없다면(=모든 정점이 포함된 사이클이 존재한다면) 0개로 취급한다.

정답 코드 및 설명

백준 20040번 - 사이클 게임 (Gold 4)와 비슷한 방식으로 접근했다.
대표 원소가 i인 집합에서 사이클이 생겼다면, parents[i]에 사이클을 표시하는 값 -1000을 넣었다.
트리의 개수를 세는 것은 그래프의 연결 요소 중 사이클이 없는 것의 개수를 세는 것이다.
배열 parents[]에 들어있는 음수인 원소의 개수가 그래프의 연결 요소의 개수이다.
이 중 사이클을 제거하려면 원소가 -1000인 경우를 빼고 세면 된다.

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

public class BOJ4803 {
    final static int CYCLE = -1000;
    int n, m;
    int[] parents;
    BufferedReader br;

    BOJ4803() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }

    void test() throws IOException {
        for (int i = 1; ; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken());
            if (n == 0 && m == 0) break;
            setGraph(n, m);
            print(i, numOfTrees());
        }
    }

    int numOfTrees() {
        int count = 0;
        for (int i = 0; i < n; i++)
            if (parents[i] < 0 && parents[i] != CYCLE)
                count++;
        return count;
    }

    void print(int i, int numOfTrees) {
        StringBuilder sb = new StringBuilder();
        sb.append("Case ").append(i).append(": ");
        if (numOfTrees == 0)
            sb.append("No trees.");
        if (numOfTrees == 1)
            sb.append("There is one tree.");
        if(numOfTrees > 1)
            sb.append("A forest of ").append(numOfTrees).append(" trees.");
        System.out.println(sb);
    }

    void setGraph(int n, int m) throws IOException {
        parents = new int[n];
        for (int i = 0; i < n; i++)
            parents[i] = -1;
        while (m-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken()) - 1;
            int end = Integer.parseInt(st.nextToken()) - 1;
            union(start, end);
        }
    }

    void union(int start, int end) {
        int setStart = findSet(start);
        int setEnd = findSet(end);
        if (setStart == setEnd) {
            parents[setStart] = CYCLE;
            return;
        }
        if (-parents[setStart] >= -parents[setEnd]) {
            if (parents[setStart] != CYCLE)
                parents[setStart] += parents[setEnd];
            parents[setEnd] = setStart;
        } else {
            if (parents[setEnd] != CYCLE)
                parents[setEnd] += parents[setStart];
            parents[setStart] = setEnd;
        }
    }

    int findSet(int index) {
        if (parents[index] < 0)
            return index;
        return findSet(parents[index]);
    }

    void solution() throws IOException {
        test();
    }

    public static void main(String[] args) throws IOException {
        new BOJ4803().solution();
    }
}