서로소 집합(Disjoint Set: Union-Find)

1. 개념

Disjoing Set란 공통 원소가 없는 "상호 배타적"인 부분 집합들로 나누어진 원소들에 대한 정보를 저장하고 조작하는 자료구조이다.

서로소 집합을 만드는 과정을 Union-Find 라고 한다.

2. 구현

Union-Find는 3가지 과정을 통해 진행된다.

    1) 초기화 : N 개의 원소가 각 정해진 초기 집합에 있도록 설정

    2) Union : 두 원소 a,b가 주어졌을 때 이들이 속한 두 집합을 하나로 합함

    3) Find : 원소 a가 주어졌을 때 이 원소의 속한 집합을 찾음

vector<int> parent, rank_cnt;

for(int i=0; i<n; i++) parent[i] = i;
int find(int u){
    if(u == parent[u]) return u;
    return parent[u] = find(parent[u]);
}
 
void union_(int u, int v){
    u = find(u); v = find(v);
 
    if(u == v) return;
    if (rank_cnt[u] > rank_cnt[v]) swap(u,v);
    parent[u] = v;
    if(rank_cnt[u] == rank_cnt[v]) rank_cnt[v]++;
}

[Union-FInd 예제 : http://gyutts.tistory.com/113?category=755806]