[C++] 디스조인트-셋(Disjoint-Set) ; 유니언-파인드(Union-Find), 서로소 집합, 상호 배타적 집합

디스조인트-셋(Disjoint-Set)

• 디스조인트-셋(Disjoint-Set) 또는 유니언-파인드(Union-Find) 자료구조
  • 다음과 같이 불림.
    • 서로소 집합 자료구조
    • 상호 배타적 집합 자료구조
  • 트리 형태로 구성된 포레스트(Forest)
  • 각각의 원소는 숫자 ID 에 의해 표현됨.
  • 랭크(Rank) 와 부모에 의한 포인터를 가짐.
  • 초기화되면 랭크가 0인 N개의 독립적인 원소가 생성됨.
    • 각각의 원소는 하나의 트리를 나타냄.
  • 공통의 원소를 갖지 않는 원소 집합을 표현하기 위해 사용됨.

 

지원 연산

make-set(x)

• x를 ID로 갖는 원소를 디스조인트-셋 자료구조에 추가함.
  • 새로 추가한 원소의 랭크 : 0
  • 원소의 부모 포인터는 자기 자신을 가리키도록 설정함.

• 그림 설명
  • 원 안에 적힌 숫자 : 원소 ID
  • 괄호 안의 숫자 : 랭크
  • 부모 원소를 가리키는 포인터는 화살표 로 나타냄.
    • 초기화 상태에서는 자기 자신을 가리킴.

find(x)

• 원소 x에서 시작해서 부모 포인터를 따라 반복적으로 이동하여 트리의 루트를 반환함.
• 루트 원소의 부모 : 루트 자신
• 위의 그림에 나타난 원소는 트리의 루트임.
  • 이들 원소에 대해 find() 연산을 수행하면 자기 자신이 반환됨.

union(x, y)

• 2개의 원소 x와 y에 대해 union() 연산을 수행하면 먼저 x와 y의 루트를 찾음.
  • 두 루트가 같을 경우
    • x와 y가 같은 트리에 속해 있음을 의미함.
    • 이 경우, 아무런 작업을 하지 않음.
  • 두 루트가 다를 경우
    • 높은 랭크 루트를 낮은 랭크 루트의 부모 로 설정함.
• union(1, 2)와 union(5, 4)를 적용한 결과

• union(x, y) 연산을 거듭할수록
  • 더 많은 트리가 병합되어 전체 트리 개수 는 줄어듦.
  • 각 트리의 크기 는 점점 거대해지게 됨.
• union(2, 3)을 적용한 결과

• union(2, 4)를 적용한 결과

 

코드

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

class DisjointSet {
    unordered_map<int, int> parent;

public:
    void makeSet(vector<int> const &wholeset) {
        for (int i : wholeset) {
            parent[i] = i;
        }
    }

    int Find(int l) {
        if (parent[l] == l) {
            return l;
        }
        return Find(parent[l]);
    }

    void Union(int m, int n) {
        int x = Find(m);
        int y = Find(n);
        parent[x] = y;
    }
};

void print(vector<int> const &universe, DisjointSet &dis) {
    for (int i : universe) {
        cout << dis.Find(i) << " ";
    }
    cout << endl;
}

int main() {
    vector<int> wholeset = {6, 7, 1, 2, 3};
    DisjointSet dis;

    dis.makeSet(wholeset);
    dis.Union(7, 6);
    print(wholeset, dis);

    if (dis.Find(7) == dis.Find(6)) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }

    if (dis.Find(3) == dis.Find(4)) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }

    return 0;
}

 

결과

6 6 1 2 3
Yes
No