Union-Find란 이름에서도 알 수 있듯, 서로소 집합 관리에 특화된 데이터 구조입니다. 이 구조는 특정 원소가 속해 있는 집합을 관리하며, 두 집합의 병합(Union)과 특정 원소가 속한 집합의 대표를 찾는 Find 연산을 지원합니다.

이 구조는림수 (Forest)로 표현할 수 있습니다. 각각의 트리가 하나의 집합을 대표하며, 트리의 모든 노드는 그 집합에 속한 원소를 나타냅니다.

예를 들어 아래 그림과 같이:

이 그림은 두 개의 집합을 나타내며, 각각의 집합은 {1,2,3,4,5}와 {6,7,8}로 이루어져 있습니다.

두 집합을 병합하는 방법은 간단합니다. 한 집합의 루트 노드를 다른 집합의 루트 노드로 연결시켜주면 됩니다:

병합 연산의 핵심은 두 집합의 대표를 같게 만드는 것입니다. 반면, 조회 연산은 해당 원소의 최상위 루트 노드를 찾는 것이며, 이는 집합에 속하는지 여부를 판별하는 데 사용됩니다. 예를 들어, 원소 x와 y가 같은 집합에 속하면 find(x)와 find(y)의 결과가 동일합니다.

기본적인 find와 union 연산의 시간 복잡도는 O(N)이며, 이는 최악의 경우 트리가 체인 구조로 될 때 발생합니다. 이를 개선하기 위해 경로 압축(Path Compression) 기법을 사용합니다. 경로 압축은 찾기 연산 중에서 현재 노드의 대표를 직접 연결시켜주는 기법으로, 시간 복잡도를 O(log N)로 개선합니다.

경로 압축 외에도 사이즈 병합(Size-based Union) 기법을 사용하면 추가적인 최적화를 얻을 수 있습니다. 사이즈 병합은 항상 더 큰 사이즈의 집합으로 더 작은 사이즈의 집합을 병합시켜주는 방법으로, 평균적인 조회 시간을 O(α(N))로 줄일 수 있습니다. α(N)은 거의 상수에 가까운 느리게 성장하는 함수입니다.

다음은 기본적인 Union-Find 구현 예제입니다:

#include<bits/stdc++.h>
using namespace std;
const int MAXN=200010;
int parent[MAXN];
int find(int x) {
    if (x != parent[x]) {
        parent[x] = find(parent[x]); // 경로 압축
    }
    return parent[x];
}
void union_set(int x, int y) {
    int fx = find(x);
    int fy = find(y);
    if (fx != fy) {
        parent[fy] = fx;
    }
}
int main() {
    // 입력 및 초기화
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        parent[i] = i;
    }
    for (int i = 0; i < m; ++i) {
        int z, x, y;
        cin >> z >> x >> y;
        if (z == 1) {
            if (find(x) != find(y)) {
                union_set(x, y);
            }
        } else if (z == 2) {
            if (find(x) == find(y)) {
                cout << "Y" << endl;
            } else {
                cout << "N" << endl;
            }
        }
    }
    return 0;
}

상기 코드는 경로 압축만을 사용한 기본적인 구현입니다. 사이즈 병합을 추가한 버전은 다음과 같습니다:

#include<bits/stdc++.h>
using namespace std;
const int MAXN=200010;
int parent[MAXN], size[MAXN];
int find(int x) {
    if (x != parent[x]) {
        parent[x] = find(parent[x]); // 경로 압축
    }
    return parent[x];
}
void union_set(int x, int y) {
    int fx = find(x);
    int fy = find(y);
    if (fx == fy) return;
    if (size[fx] < size[fy]) {
        parent[fx] = fy;
        size[fy] += size[fx];
    } else {
        parent[fy] = fx;
        size[fx] += size[fy];
    }
}
int main() {
    // 입력 및 초기화
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        parent[i] = i;
        size[i] = 1;
    }
    for (int i = 0; i < m; ++i) {
        int z, x, y;
        cin >> z >> x >> y;
        if (z == 1) {
            if (find(x) != find(y)) {
                union_set(x, y);
            }
        } else if (z == 2) {
            if (find(x) == find(y)) {
                cout << "Y" << endl;
            } else {
                cout << "N" << endl;
            }
        }
    }
    return 0;
}

이 버전은 사이즈 병합을 통해 더 나은 성능을 제공합니다. 경로 압축과 사이즈 병합을 동시에 사용하면 거의 최적의 성능을 얻을 수 있습니다.