서로소 집합 (Union-find tree. Disjoint - set)

엄~청 짜기 쉽고 유용한 트리.

유니온 파인드 트리라고만 부르고 있었는데, 서로소 집합이라는 말이 더 나은거 같다. 

기본적으로 루트가 하나 있고, 이 루트를 parent로 가지는 노드가 주렁주렁 달린 트리이다.

두가지 연산을 지원하는데,

1. p의 루트를 부르는 find(p)

2. p와 q를 같은 집합에 넣는 union(p,q)

아무 생각없이 짜면

int parent[1000], size[1000];

void init(){
    for (int i=0; i<1000; i++) {
        parent[i] = i;
        size[i] = 1;
    }
}
int find(int p){
    if(parent[p] == p) return p;
    else return find(parent[p]);
}

void uni(int p, int q){
    p = find(p);
    q = find(q);
    parent[p] = q;
    size[q] += size[p];
}

이렇다.

이러면 쓰기는 편하지만 빠르지는 않다. (아마 원소 n개 넣으면 최대 O(n^2)..?)

하지만 개선할 수 있다.

* 1. 만약에 5 -> 4 -> 3 -> 2 -> 1 이런 식으로 트리가 달려있다 치자.

그러면 find(5)를 부르면 4번 정도를 거쳐서 1이 나올 것이다.

이럴 바에 그냥 parent[5] = 1로 압축을 해주면 한번에 갈텐데..

그래서, find(p)를 부를 때 압축까지 해줄 수 있다.

int find(int p){
    if(parent[p] == p) return p;
    else return parent[p] = find(parent[p]);
}

이렇게 하면, parent[5] = parent[4] .... = 1로 경로를 압축해 줄 수 있다.

* 2. 얘도 트리다 보니까 편중되는 (skewed) 것을 막을 수가 없다.

이진 탐색 트리하고 비슷한데, 해결책은 두가지가 있다.

1. 근본적인 해결책이다. rank를 만들어서 그 트리의 깊이를 대략 저장한다. (완벽하게 저장하진 않는다.)

int parent[1000], size[1000], rank[1000];

void init(){
    for (int i=0; i<1000; i++) {
        parent[i] = i;
        size[i] = 1;
        rank[i] = 0;
    }
}

void uni(int p, int q){
    p = find(p);
    q = find(q);
    if(rank[p] < rank[q]) parent[p] = q, size[q] += size[p];
    else parent[q] = p, size[p] += size[q];;
    if(rank[p] == rank[q]) rank[p]++;
}

여기서 rank는 트리의 크기는 아니더라도 트리의 크기에 비례하는 값들이다. (rank가 높으면 작은 걸로 반대로 알았음 ㅠㅠ 늦게나마 수정합니다.) 작은 애들을 큰 애에 옮겨 주는 것이 이득이리라.

rank 대신 size를 써도 똑같은 효과를 볼 수 있다.

2. 이진 탐색 트리의 Treap과 비슷한 방법이다.

야매에 가까우니 까먹었을때만 쓰자

int parent[1000], size[1000];

void uni(int p, int q){
    p = find(p);
    q = find(q);
    if(rand()&1) parent[p] = q, size[q] += size[p];
    else parent[q] = p, size[p] += size[q];;
}

처음 들었을 때 약간 벙쪘던 방법인데.. 뭐. 안될건 없지 않는가.

1번 방법을 까먹었을 때 유용하지만. 1번 방법이 뭐 레드 블랙 트리 구현하는 것도 아니고.. 그냥 알아만 두자.

서로소 집합의 시간복잡도를 설명할때는 생전 처음 보는 기호가 등장한다.

인데, 에커먼 함수의 역함수이다.

저게 얼마나 작냐면 거의 10^10000000 정도의 n이 들어와도 4밖에 안되고, 보통 10만 정도 들어오는데 이때도 4다.

아마 이진 탐색 트리에 붙어있는 계수보다도 작을 듯.

그래서 보통은 union. find 연산 모두 O(1)으로 간주한다. 계산할때도 그렇게 계산하면 된다.

만약에 연습해보고 싶으면

 * 최소 신장 트리 구해보기 (Kruskal Algorithm) 아마 프림 알고리즘에는 손도 안 대게 될 것이다. 구현하기 매우 편하다.

* http://koistudy.net/?mid=prob_page&NO=962

* https://www.acmicpc.net/problem/2463

를 풀어보는 것을 추천한다.