[백준 Java] 11724 연결 요소의 개수

문제 링크

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

풀이

유니온 파인드를 사용했다

• find : 배열의 값(부모)이 들어온 숫자와 같다면 그 값을 돌려준다. 다르다면 부모의 값을 계속 타고 올라가며 찾는다.
• union : find를 사용하여 각 부모를 찾는다. 두 값의 부모가 같다면 false를 돌려준다. 값이 다를 경우 작은 쪽을 부모로 만들어주고 true를 돌려준다

마지막에 N만큼 순회하며 부모의 값을 집합에 넣어주고, 집합의 크기를 출력한다.

코드

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 Main {
    static int N, parent[];

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

        N = Integer.parseInt(tokens.nextToken());
        int M = Integer.parseInt(tokens.nextToken());

        parent = new int[N];

        initArr();

        for (int i = 0; i < M; i++) {
            tokens = new StringTokenizer(br.readLine());
            union(Integer.parseInt(tokens.nextToken()) - 1, Integer.parseInt(tokens.nextToken()) - 1);
        }

        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < N; i++) {
            set.add(find(i));
        }
        System.out.println(set.size());
    }

    private static void initArr() {
        for (int i = 0; i < N; i++) {
            parent[i] = i;
        }
    }

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

    private static boolean union(int a, int b) {
        a = find(a);
        b = find(b);

        if (a == b) return false;

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