유니온 파인드(Union find) & 서로소 집합(Disjoint Set)?

---

Union find는 대표적인 그래프 알고리즘으로

집합 내의 요소의 연결성을 효율적으로 추적하는 데 사용되는 데이터 구조 및 알고리즘입니다.

역으로 서로 연결되어 있지 않은 노드를 판별할 수도 있기 때문에 서로소 집합 (Disjoint-set)이라고도 합니다.

알고리즘은 union과 find의 두 가지 연산으로 구성되어 있습니다.

-> union 은 각 노드가 속한 집합을 1개로 합치는 연산

-> find 특정 노드 A에 관해 A가 속한 대표 노드를 반환하는 연산

Union-Find 알고리즘은 집합 내 요소의 연결성을 추적하는 데 유용한 데이터 구조 및 알고리즘입니다.

이것은 많은 그래프 알고리즘에서 사용될 수 있으며 경로 압축 최적화로 O(log n) ~ O(n)의 시간 복잡도를 가집니다.

예제 코드 C++

---

#include <iostream>
#include <vector>

using namespace std;

// Initialize the parent array
void makeSet(int parent[], int n) {
    for (int i = 0; i < n; i++) {
        parent[i] = i;
    }
}

// Find the root of the set containing node x
int find(int parent[], int x) {
    if (parent[x] != x) {
        parent[x] = find(parent, parent[x]); // Path compression
    }
    return parent[x];
}

// Merge the sets containing nodes x and y
void unite(int parent[], int x, int y) {
    int rootX = find(parent, x);
    int rootY = find(parent, y);
    parent[rootY] = rootX; // Make rootX the parent of rootY
}

int n = 5; // Number of nodes
int parent[5]; // Number of nodes

int main() {


    makeSet(parent, n); // Initialize the parent array

    // Merge sets containing nodes 2 and 4
    unite(parent, 2, 4);

    // Merge sets containing nodes 1 and 5
    unite(parent, 1, 5);

    // Merge sets containing nodes 1 and 2
    unite(parent, 1, 2);

    // Find the set of node 4
    int root4 = find(parent, 4);

    // Print the parent array
    for (int i = 0; i < n; i++) {
        cout << parent[i] << " ";
    }
    cout << endl;

    // Print the root of the set containing node 4
    cout << "The root of the set containing node 4 is " << root4 << endl;

    return 0;
}

백준 예제

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

#include <iostream>

using namespace std;

constexpr int Max = 1000001;

// 유니온 root노드 배열
int uArr[Max];

int N, M, u, b, c;

//부모를 찾는 함수
//모든 경로가 부모를 가르키게 함
//상수 시간의 복잡도
int Find(int x)
{
    if (uArr[x] == x) return x;
    return uArr[x] = Find(uArr[x]);
}

//두 노드를 연결 시키는 것
//기준을 정해서 연결시키는 것이 헷갈리지 않음
//작은쪽이 부모 or 큰쪽이 부모
void Union(int x, int y)
{
    x = Find(x);
    y = Find(y);

    if (x != y) {
        if (x < y) uArr[y] = x;
        else uArr[x] = y;
    }
}

int main()
{
    ios_base::sync_with_stdio(false); // scanf와 동기화를 비활성화
    // cin.tie(null); 코드는 cin과 cout의 묶음을 풀어줍니다.
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N >> M;
    // 유니온 배열 초기화
    for (int i = 0; i <= N; i++) uArr[i] = i;

    for (int i = 0; i < M; i++) {

        cin >> u >> b >> c;

        if (u == 0) { // 합집합 연산
            Union(b, c);
        }
        else { // 질의
            if (Find(b) != Find(c)) cout << "NO\n";
            else cout << "YES\n";
        }
    }

    return 0;
}

백준 Union find Algorithm 문제

---

https://www.acmicpc.net/problemset?sort=ac_desc&algo=81