[Algorithm] Union-Find Algorithm

Union-Find 알고리즘은 그래프 알고리즘 중 하나로 “합집합 찾기”를 위해 사용되는 대표적인 알고리즘이다. 사용되는 연산 과정은 다음과 같다.

Find: x가 어떤 집합에 속해있는지 찾는 연산
Union: x와 y가 속한 집합을 합치는 연산

Example

Step 1

우선 초기 상태를 예시를 위처럼 들었다. Table을 node ID와 group ID를 동일하게 맞췄다.

Step 2

만약 union(1, 2), union(3, 4) 동작이 수행된다고 했을 때 위 그림과 같이 수행이 될 것이다.

Step 3

그 뒤에 union(2, 3)이 수행된다고 했을 때는 위 그림과 같이 node 2와 node 3이 바로 붙는게 아니라 node 2의 parent를 찾아서 node 1과 node 3이 붙도록 된다. 이렇게 graph가 만들어지게 되면 parent를 찾는 depth가 짧아지는 효과가 발생해 시간 복잡도는 O(logN)이 된다.

Source Code

이제 위 동작을 구현하는 코드를 보면 아래와 같이 구현 할 수 있다.

#include <iostream>

#define MAX 1000000+1

using namespace std;

int N, M;
int g_table[MAX];

int getGrp(int _v)
{
    if (_v == g_table[_v])
        return _v;
    else {
        g_table[_v] = getGrp(g_table[_v]);
        return g_table[_v];
    }
}

bool isDiffGrp(int _a, int _b)
{
    int ga = getGrp(_a);
    int gb = getGrp(_b);

    return (ga != gb) ? true : false;
}

void doUnion(int _a, int _b)
{
    int ga = getGrp(_a);
    int gb = getGrp(_b);

    if (ga != gb) {
        g_table[ga] = gb;
    }
}
int main()
{
    cin.tie(0);
    cin.sync_with_stdio(false);
    ios_base::sync_with_stdio(false);

    cin >> N >> M;

    for (int i=0; i<=N; i++)
        g_table[i] = i;

    for (int i=0; i<M; i++) {
        int op, a, b;
        cin >> op >> a >> b;

        if (op == 0) {
            doUnion(a, b);
        } else {
            if (isDiffGrp(a, b)) {
                printf("%s\n", "NO");
            } else {
                printf("%s\n", "YES");
            }
        }
    }

    return 0;
}

$ ./a.out
7 8
0 1 3
1 1 7
0 7 6
1 7 1
0 3 7
0 4 2
0 1 1
1 1 1
NO
NO
YES

Reference

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