간단하게 구현하는 Disjoint set

2018-06-20 01:09:45 | 조회수 2062


서로소 집합 자료구조를 표현하기 위한 자료구조의 형태로, 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];

}


간단하게 구현하는 Disjoint set - 알고리즘닷컴
14 개의 글