서로소 집합

서로소 집합

• 교집합이 공집합으로 이루어진 여러 집합들의 모음.

Union Find

• Init: 모든 원소들이 자기 자신을 가지도록 초기화해줌.
• Union(X, Y): X가 속한 부분과 Y가 속한 집합을 병합함.
• Find(v): v가 속한 집합의 번호를 반환해 줌.

구현하기

Init연산

• 배열 상태를 자기 자신으로 향하게 초기화한다.

int d[300004];
for(int i=1;i<=n;i++) d[i]=i;

 

Find 연산

• Find 연산과 같은 경우에는 루트 노드를 찾아가서 반환해 주면 된다.

int f(int x) {
    if (x == d[x]) return x;
    return d[x] = f(d[x]);
}

Find 연산

Union 연산

• 각각의 루트를 Find로 찾은 다음에 서로 다른 집합이라면 같은 집합으로 연결해 준다.

void g(int x, int y) {
    int X = f(x), Y = f(y);
    if (X != Y) d[X] = Y;
}

Union연산

 

예시 문제

BOJ Traveling SCCC President

 문제 설명

• 문제의 내용이 많지만 결론적으로는 모든 건물을 이동해야 하는 최소 스패닝 트리를 사용해야 하는 문제이다.
• 즉 유니온 파인드를 사용하여서 가중치값에 따라서 정렬을 한 다음, 유니온 파인드를 사용하여서 모든 노드를 연결하는 경우를 구해주면 된다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int n, m, k;
int d[300004];
vector<pair<pair<int, int>, int>> v;
vector<int> v1;
bool compare(pair<pair<int, int>, int> &x, pair<pair<int, int>, int> &y) {
    return x.second < y.second;
}
//Find
int f(int x) { 
    if (x == d[x]) return x;
    return d[x] = f(d[x]);
}
//Union
void g(int x, int y) {
    int X = f(x), Y = f(y);
    if (X != Y) d[X] = Y;
}
int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) d[i] = i;
    for (int i = 1, x, y, z; i <= m; i++) {
        cin >> x >> y >> z;
        v.push_back({{x, y}, z});
    }
    v1.resize(n + 1); 
    for (int i = 1; i <= n; i++) cin >> v1[i];
    int ans = 0;
    sort(v.begin(), v.end(), compare);
    for (auto i : v) {
        int x = i.first.first, y = i.first.second, w = i.second;
        if (f(x) != f(y)) {
            g(x, y);
            ans += w;
        }
    }
    cout << ans;
}