[BOJ/JAVA] 4803번: 트리

4803번: 트리

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 n ≤ 500과 m ≤ n(n-1)/2을 만족하는 정점의 개수 n과 간선의 개수 m이 주어진다. 다음 m개의 줄에는 간선을 나타내는 두 개의 정수가 주어진다. 같은 간선은 여러 번 주어지지 않는다. 정점은 1번부터 n번까지 번호가 매겨져 있다.

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

키워드

• 트리는 사이클이 없는 연결 요소

• 트리는 정점이 n개, 간선이 n-1개

• 임의의 두 정점에 대해서 경로가 유일

• 그래프가 주어졌을 때, 트리의 개수를 세는 프로그램

---

구현

• DisjontSet을 이용하여 트리인지를 판단하였다.

• cycle[]
  • 해당 노드가 사이클에 속하는지 판단하는 배열

• ★merge★ :: 핵심 메소드
  1. 두 노드가 주어졌을 때 두 노드의 부모노드를 찾는다.
  2. 두 부모노드 중 하나라도 사이클에 포함된다면 다른 하나를 사이클노드로 바꾼다.
  3. 두 부모 노드가 같은 노드라면, 사이클에 포함시키고 종료한다.
  4. 두 노드를 하나로 합친다.

1. 모든 노드의 입력이 끝나면, 각 노드를 돌면서 부모노드를 찾는다.

2. 해당 노드가 사이클이라면 카운트를 하지 않는다.

3. 사이클이 아니라면 집합(resultSet)에 추가한다.

4. 반복문이 끝나면 배열의 크기를 구한다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class java_4803 {
    static int n;
    static DisjointSet disjointSet;
    // 사이클인가? 아닌가?
    static boolean cycle[];

    static class DisjointSet {
        int parent[];

        public DisjointSet() {
            parent = new int[n];
            for (int i = 0; i < parent.length; i++) {
                parent[i] = i;
            }
        }

        public int getParent(int index) {
            if (index == parent[index]) {
                return index;
            }

            parent[index] = getParent(parent[index]);

            return parent[index];
        }

        // 사이클이면 True
        // 정상이면 False
        public void merge(int u, int v) {
            u = getParent(u);
            v = getParent(v);

            if (cycle[u] || cycle[v]) {
                cycle[u] = true;
                cycle[v] = true;
            }

            if (u == v) {
                cycle[u] = true;
                return;
            }

            parent[v] = u;

            return;
        }

    }

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



        /*
         * 그래프에서 어떻게 트리를 추출하는가?
         * 단순하게 트리인지 아닌지를 어떻게 아는가?
         * 1. 사이클이 없어야 한다.
         * 2. 정점이 n개 간선이 n-1개 있어야 한다.
         * 3. 두 정점 사이의 경로가 유일하다.
         * 4. 스패닝 트리
         *
         * 스패닝 트리 -> 크루스칼 알고리즘
         * DisjointSet -> 상호 배제 집합
         *
         */

        // 루프가 있는지 탐색할 것
        //
        int testCase = 1;
        while (true) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());

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

            disjointSet = new DisjointSet();
            cycle = new boolean[n];

            for (int i = 0; i < m; i++) {
                st = new StringTokenizer(br.readLine());
                int from = Integer.parseInt(st.nextToken()) - 1;
                int to = Integer.parseInt(st.nextToken()) - 1;

                disjointSet.merge(from, to);
            }

            Set<Integer> resultSet = new HashSet<>();
            for (int i = 0; i < n; i++) {
                int node = disjointSet.getParent(i);
                // 사이클
                if (cycle[node]) {
                    continue;
                }
                resultSet.add(node);
            }

            int result = resultSet.size();

            if (result == 0) {
                System.out.printf("Case %d: No trees.\n", testCase++);
                continue;
            }

            if (result == 1) {
                System.out.printf("Case %d: There is one tree.\n", testCase++);
                continue;
            }

            System.out.printf("Case %d: A forest of %d trees.\n", testCase++, result);

        }

        br.close();
    }
}

---

Uploaded by N2T