[SWEA] 카풀 그룹 나누기 (Java)

1. 문제 요약

직원 1~N번이 있다. M장의 신청서가 각각 두 사람을 묶는다. 신청서를 타고 간접적으로 이어지는 사람도 모두 같은 그룹이 된다. 최종 그룹이 몇 개인지 구한다.

• 2 ≤ N ≤ 100, 1 ≤ M ≤ 100
• 신청서에 이름이 없는 직원은 혼자서 한 그룹

2. 접근 과정

문제를 그래프로 번역하기

직원을 정점, 신청서를 간선으로 보면 이 문제는 그래프의 연결 요소 개수 세기다.

3. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;

public class Solution {

    static int[] parent;

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

        in.nextToken();
        int T = (int) in.nval;

        for (int tc = 1; tc <= T; tc++) {
            in.nextToken(); int n = (int) in.nval;
            in.nextToken(); int m = (int) in.nval;

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

            for (int i = 0; i < m; i++) {
                in.nextToken(); int a = (int) in.nval;
                in.nextToken(); int b = (int) in.nval;
                union(a, b);
            }

            int groups = 0;
            for (int i = 1; i <= n; i++) {
                if (find(i) == i) groups++;
            }

            sb.append('#').append(tc).append(' ').append(groups).append('\n');
        }

        System.out.print(sb);
    }

    static int find(int x) {
        if (parent[x] == x) return x;
        return parent[x] = find(parent[x]);
    }

    static void union(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);
        if (rootA == rootB) return;
        parent[Math.max(rootA, rootB)] = Math.min(rootA, rootB);
    }
}

시간복잡도: O(N + M·α(N))
공간복잡도: O(N) — parent 배열