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

백준 11724 연결 요소의 개수

Union Find를 활용하는 문제다. 일반적으로 유니온 파인드 문제는 부모를 찾는 함수, 부모가 같은지 확인하는 함수, 부모를 통합하는 함수 3가지를 만들지만 문제가 간단해서 2개의 함수만 만들었다.

1. 배열에 저장된 값은 해당 인덱스의 부모다
2. 기본값은 자기 자신이지만 부모가 자기 자신이 아니라면, 부모를 찾는다.
3. 두 노드가 부모를 찾았다면 더 작은 값으로 부모를 통합한다.

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

public class Main {
    static int []p;
    static HashSet <Integer> hs = new HashSet<>();
    static int parent(int a){
        while(p[a] != a){
            a = p[a];
        }
        return p[a];
    }

    static void union(int a, int b){
        int ap = parent(a);
        int bp = parent(b);
        if(ap != bp){
            if(ap > bp){
                p[ap] = bp;
                hs.remove(ap);
            } else{
                p[bp] = ap;
                hs.remove(bp);
            }
        }
    }

    public static void main(String[] args) {
        try {
            int n, m;
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
            StringTokenizer st= new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken());
            p = new int [n + 1];
            for(int i = 1; i <= n; i ++){
                hs.add(i);
                p[i] = i;
            }
            while(m-- > 0){
                st= new StringTokenizer(br.readLine());
                union(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
            }
            System.out.println(hs.size());
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}