Data Structures

1.7 Disjoint Set

개념

서로소 집합 자료구조(DSU)는 집합을 합치는 과정에서 두 원소가 같은 집합에 속하는지 빠르게 확인할 때 사용합니다. 서로 겹치지 않는 집합들을 관리하며, 각 집합에는 대표 원소가 있습니다.

  • Find: 원소가 속한 집합의 대표를 찾습니다. 두 원소의 대표가 같으면 같은 집합에 속합니다.
  • Union: 두 원소가 속한 집합을 하나로 합칩니다.

현재 원소들이 1,21,2가 속한 집합, 33만 속한 집합, 4,54,5가 속한 집합으로 나뉘어 있습니다. 11과 22는 같은 집합에 속하고, 22와 33은 서로 다른 집합에 속합니다.

1 2 3 4 5
▲ [그림 1] 서로소 집합의 합치기 — 연산 전

22와 33이 속한 집합을 합치면 1,2,31,2,3이 한 집합이 됩니다. 이제 22와 33의 대표가 같으므로 같은 집합에 속한다고 판별합니다.

1 2 3 4 5
▲ [그림 2] 서로소 집합의 합치기 — 연산 후

부모 배열로 각 집합을 트리로 표현합니다. 대표 정점의 부모는 자기 자신입니다. 부모를 따라가 찾은 대표가 같으면 같은 집합입니다.

경로 압축

경로 압축은 Find로 대표를 찾은 뒤, 경로에 있는 원소들의 부모를 대표로 바꾸는 방법입니다. 이후 같은 경로를 탐색할 때 거치는 원소 수가 줄어듭니다.

경로 절반 압축(Path Halving)은 탐색 중 현재 원소의 부모를 조부모로 바꾸고, 바뀐 부모로 이동하는 방법입니다.

Union by Size

집합의 원소 수를 기준으로 합칩니다. 각 대표에 집합의 원소 수를 저장하고, 작은 집합의 대표를 큰 집합의 대표 아래에 붙입니다. 합친 집합의 크기는 두 집합의 원소 수를 더한 값입니다. 크기가 같으면 어느 쪽을 대표로 선택해도 됩니다.

Union by Rank

트리 높이의 상한을 나타내는 rank를 기준으로 합칩니다. 원소 하나로 이루어진 트리의 rank는 00입니다.

  • rank가 다르면 작은 쪽의 대표를 큰 쪽의 대표 아래에 붙입니다. 새 대표의 rank는 기존 값을 유지합니다.
  • rank가 같으면 한쪽 대표를 다른 쪽 아래에 붙이고, 새 대표의 rank를 11 늘립니다.

경로 압축으로 트리 높이가 줄어들어도 rank는 유지하며, 이후 합칠 방향을 정하는 기준으로 사용합니다.

Union by Size와 Union by Rank는 각각 원소 수와 rank를 비교하는 합치는 방법입니다. 두 방식 모두 대표가 이미 같으면 합치기를 마칩니다.

시간·공간복잡도

초기화는 O(N)O(N), 공간은 O(N)O(N)입니다. Union by Size 또는 Union by Rank에 경로 압축이나 경로 절반 압축을 함께 적용하면 연산의 분할 상환 비용은 O(α(N))O(\alpha(N))입니다. α(N)\alpha(N)은 매우 느리게 증가하는 함수입니다.

예제

문제

11번부터 NN번까지의 원소가 처음에는 각각 하나의 집합을 이룬다. 다음 명령을 순서대로 수행하여라.

명령동작
union a b두 원소가 속한 집합을 합친다.
same a b같은 집합이면 YES, 서로 다른 집합이면 NO를 출력한다.
size a원소 aa가 속한 집합의 원소 수를 출력한다.

입력

첫째 줄에 원소 수 NN과 명령 수 QQ가 공백을 사이에 두고 주어진다. 1≤N,Q≤10 0001\le N,Q\le10\,000이다.

다음 QQ개 줄에 위 표의 형식으로 명령이 하나씩 주어진다. 명령과 인자는 공백을 사이에 두고 주어진다. 원소 번호 a,ba,b의 범위는 1≤a,b≤N1\le a,b\le N이다.

출력

same과 size 명령의 결과를 한 줄에 하나씩 출력한다.

예제 입력

5 7
same 1 2
union 1 2
union 2 3
same 1 3
size 2
union 1 3
size 1

예제 출력

NO
YES
3
3

예제 코드

C++20

#include <iostream>
#include <string>
#include <utility>

using namespace std;

const int N = 10000;
int p[N + 1], sz[N + 1];

int find(int x) {
    while (p[x] != x) {
        p[x] = p[p[x]]; // 경로 절반 압축
        x = p[x];
    }
    return x;
}

// Union by Size: 집합의 원소 수를 기준으로 합침
void unite(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b) return;
    if (sz[a] < sz[b]) swap(a, b);
    p[b] = a;
    sz[a] += sz[b]; // 합친 집합의 원소 수 갱신
}

int main() {
    int n, q, i, a, b;
    string op;

    cin >> n >> q;

    for (i = 1; i <= n; ++i) {
        p[i] = i;
        sz[i] = 1;
    }

    for (i = 0; i < q; ++i) {
        cin >> op >> a;

        if (op == "size") cout << sz[find(a)] << '\n';
        else {
            cin >> b;

            if (op == "union") unite(a, b);
            else if (find(a) == find(b)) cout << "YES\n";
            else cout << "NO\n";
        }
    }
}