[백준]#4803 트리

문제

그래프는 정점과 간선으로 이루어져 있다. 두 정점 사이에 경로가 있다면, 두 정점은 연결되어 있다고 한다. 연결 요소는 모든 정점이 서로 연결되어 있는 정점의 부분집합이다. 그래프는 하나 또는 그 이상의 연결 요소로 이루어져 있다.

트리는 사이클이 없는 연결 요소이다. 트리에는 여러 성질이 있다. 예를 들어, 트리는 정점이 n개, 간선이 n-1개 있다. 또, 임의의 두 정점에 대해서 경로가 유일하다.

그래프가 주어졌을 때, 트리의 개수를 세는 프로그램을 작성하시오.

입력

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

출력

입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다.

예제 입력 1

6 3
1 2
2 3
3 4
6 5
1 2
2 3
3 4
4 5
5 6
6 6
1 2
2 3
1 3
4 5
5 6
6 4
0 0

예제 출력 1

Case 1: A forest of 3 trees.
Case 2: There is one tree.
Case 3: No trees.

풀이

이 문제는 Find-Union(분리집합) 알고리즘을 이용해서 풀 수 있었다. 분리집합을 이용해서 각 트리의 루트를 구해 트리의 개수를 구하고 그 중에서 싸이클이 있는 트리를 빼주는 방식이다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashSet;

public class Main {
    static int[] parent;

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

        while(true) {
            String[] input = br.readLine().split(" ");
            int n = Integer.parseInt(input[0]);
            int m = Integer.parseInt(input[1]);
            HashSet<Integer> tree = new HashSet<>();      //트리형성된 루트 저장
            HashSet<Integer> cycles = new HashSet<>();    //싸이클 생성된 노드들 저장

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

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

            for(int i=0; i<m; i++) {
                input = br.readLine().split(" ");
                int a = Integer.parseInt(input[0]);
                int b = Integer.parseInt(input[1]);

                if(find(a)==find(b))      //유니온 전에 parent가 같으면 싸이클 생성됨
                    cycles.add(a);

                union(a, b);
            }

            for(int i=1; i<=n; i++)     //루트들 저장해서 트리 개수 체크
                tree.add(find(i));

            int cnt = tree.size();
            boolean[] visited = new boolean[n+1];   //싸이클 생성된 트리의 루트 방문체크

            for(int c : cycles) {       //싸이클 생성된 트리의 노드들
                int x = find(c);        //노드들의 루트
                if(!visited[x] && tree.contains(x)) {
                    visited[x] = true;
                    cnt--;
                }
            }

            if(cnt<=0)
                sb.append("Case "+test_case+": No trees.\n");

            else if(cnt==1)
                sb.append("Case "+test_case+": There is one tree.\n");

            else
                sb.append("Case "+test_case+": A forest of "+cnt+" trees.\n");

            test_case++;
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }

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

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

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

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