Union-Find, Disjoint Set

상호배타적 집합( 서로소집합 )을 표현할때 쓰는 자료구조.

초기에 모든 노드의 부모노드를 자기자신으로 초기화한다.

find연산
어떤 노드가 포함된 집합이 어딘지 알기 위해서는 그 노드 자신이 부모노드인 노드가 나올때가지 노드의 부모노드를 타고 올라간다. 이때 이 노드가 그 집합을 대표하는 노드가 되며 만약 어떤 다른 두 노드를 find연산한 결과가 같다면 그 둘은 같은 집합안에 있다.
나중에 find연산시 드는 시간을 줄이기 위해 path compression을 사용 할 수 있다.
(return parent[x] = findSet(parent[x])로 부모노드를 바로 이어준다.)

union연산
두 집합을 합치는 연산, 어떤 한 집합을 대표하는 노드의 부모노드를 다른 한쪽의 대표노드로 바꿔주면 된다. 이때 find연산시 지나가는 노드 숫자를 줄이기 위해 rank를 비교하여 그에 따라 어떤 집합이 parent가 될지 정한다. (path compression때문에 정확한 rank를 보존 할 수는 없다.)

관련문제

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

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

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

http://codeforces.com/problemset/problem/500/B

void init(){
    for(int i=0;i<n;++i) parent[i]=i;
}

int findSet(int x){
    if(x==parent[x]) return x;
    return parent[x] = findSet(parent[x]);
}

void unionSet(int a, int b){
    a = findset(a);
    b = findSet(b);
    if(a==b)return;
    if(rank[a]>rank[b]) parent[b] = a;
    else parant[a] = b;
    if(rank[a]==rank[b]) ++rank[b];
}