[Computer Algorithms] Disjoint-Set : Union-Find (서로소 집합)

1. 각 노드의 부모를 자기 자신으로 초기 설정한다.

2. Find는 한 set에 있는 노드들의 부모 노드로의 경로를 압축하여 노드들이 공통된 하나의 부모 노드를 가리키게 하고, 이를 return하게 한다.

3. Union는 두 노드의 부모 노드를 비교하여 큰 수의 부모 노드가 작은 수의 부모 노드의 자식 노드가 되게 한다.

 

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

int V, E;
int parent[101];

int find_parent(int x)
{
    if (parent[x] != x)
        parent[x] = find_parent(parent[x]);
    return parent[x];
}

void union_parent(int x, int y)
{
    x = find_parent(x);
    y = find_parent(y);
    if (x < y)
        parent[y] = x;
    else
        parent[x] = y;
}

void input()
{
    cin >> V >> E;
    for (int i = 1; i <= V; i++)
        parent[i] = i;

    for (int i = 0; i < E; i++)
    {
        int x, y;
        cin >> x >> y;
        union_parent(x, y);
    }
}

void output()
{
    cout << "각 원소가 속한 집합: ";
    for (int i = 1; i <= V; i++)
        cout << find_parent(i) << " ";
    cout << endl;
    cout << "부모 테이블: ";
    for (int i = 1; i <= V; i++)
        cout << parent[i] << " ";
    cout << endl;
}

int main(void)
{
    input();
    output();
    return 0;
}

 

시간 복잡도: O(V+MlogV)