서로소 집합 자료구조를 표현하기 위한 자료구조의 형태로, Union(합치기) 연산과 Find(찾기) 연산의 2가지 연산을 지원합니다. 이 연산을 최소 스패닝 트리를 계산하는 크루스칼 알고리즘을 구현할 때 사용되는 것을 예로 들 수 있습니다. 기본적으로 Union 연산은 트리 구조를 이용하여 집합을 저장하는데, 이때 최적화를 하지 않으면 $N$개의 원소에 대해 최대 높이가 $N-1$의 트리가 만들어질 경우, $O(N)$의 시간복잡도가 형성되므로 이를 최적화 해주는 과정이 필요합니다.
따라서 Union 연산으로 생성되는 트리의 편중(skewed) 현상을 해결하기 위해서는 트리의 깊이에 따른 rank를 매겨 항상 랭크가 작은 쪽을 큰 쪽으로 붙이는 Union-by-rank로 이를 최적화 할 수 있습니다.
typedef long long ll;
const int usize = 1011;
ll u_parent[usize], u_rank[usize], u_size[usize];
int find(int n)
{
return n == u_parent[n] ? n : u_parent[n] = find(u_parent[n]);
}
void Union(int a, int b)
{
a = find(a), b = find(b);
if (u_rank[a] < u_rank[b])
u_parent[a] = b, u_size[b] += u_size[a];
else
u_parent[b] = a, u_size[a] += u_size[b];
u_rank[a] += u_rank[a] == u_rank[b];
}