Disjoint-set - 유니온-파인드 구현

#include <iostream>
#include <vector>
using namespace std;
vector<int> parents;     //parents[i] = i의 부모 노드. 만일 parents[i] == i라면 i가 바로 집합의 루트 노드임. main에서 문제에 주어진대로 알아서 초기화할것.
vector<int> depth;        //depth[i] = i라는 set의 깊이(단, i가 루트 노드일 때만 유효). 처음에는 모두 1로 초기화할것.

int findSet(int a) {
    if (parents[a] == a) return a;                 //루트 노드이므로 자신 반환.
    return parents[a] = findSet(parents[a]);    //부모의 부모의 부모의.... 로 자신이 속한 집합의 루트 노드까지 거슬러올라감. 동시에 그 루트 노드 값으로 경로를 최적화 해줌.
}

void unionSet(int a, int b) {
    int ra = findSet(a);                //a가 속한 집합
    int rb = findSet(b);                //b가 속한 집합

    if (ra == rb) return;              //이미 같은 집합이면 합치지 않음.

    if (depth[ra] > depth[rb]) swap(ra, rb);        //비대칭을 해결하기 위해 두 집합 중 더 깊이가 얕은 것을 깊은 것의 밑으로 붙여줄 것이다.
    parents[ra] = rb;

    if (depth[ra] == depth[rb]) depth[rb]++;      //만일 두 집합의 깊이가 동일했다면 최종 집합의 깊이가 하나 더 깊어진다. 
}