Union & Find 알고리즘

    static int N;
    static int[] parents;
 
    // 단위집합 생성
    static void makeSet() {
        parents = new int[N];
 
        // 자신의 부모노드를 자신의 값으로 세팅
        for (int i = 0; i < N; i++)
            parents[i] = i;
 
    }
 
    // a의 집합 찾기 : a의 대표자 찾기
    static int findSet(int a) {
        if (a == parents[a])
            return a;
        // 내 부모를 찾고 찾아온 부모로 갱신
        return parents[a] = findSet(parents[a]); // path compression
    }
 
    static boolean union(int a, int b) {
        int aRoot = findSet(a);
        int bRoot = findSet(b);
        if (aRoot == bRoot)
            return false;
 
        parents[bRoot] = aRoot;
        return true;
    }