Disjoint Set

Disjoint Set은 상호배타적 집합을 나타내는 자료구조를 말한다. disjoint-set data structure, union–find data structure, merge–find set 이라고도 불린다. 

크게 초기화, Union(Merge) 연산, Find 연산으로 나뉜다. 

랭크에 의한 최적화(union-by-rank), 경로 압축 최적화(path compression)를 통해 Find연산의 시간 복잡도를 줄일 수 있다.

#include <stdio.h>
#define N 100
 
int p[N];        // Parent
int rank[N];    // 트리의 높이
 
int FindSet(int x)
{
    if (p[x] == x) return x;
    else return p[x] = FindSet(p[x]);
}
 
void CreateSet()
{
    for (int i = 0; i < N; i++)
    {
        p[i] = i;
        rank[i] = 0;
    }
}
 
void MergeSet(int x, int y)
{
    x = FindSet(x);
    y = FindSet(y);
 
    if (rank[x] > rank[y])
    {
        p[y] = x;
    }
    else
    {
        p[x] = y;
        if (rank[x] == rank[y]) rank[y]++;
    }
}