[알고리즘] Union-find(합집합 찾기)

Union-find란?

 

합집합을 찾는 알고리즘이다.

구체적으로 여러 개의 노드가 존재할 때 두 개의 노드를 선택해

두 노드를 같은 집합으로 합치거나, 현재 이 두 노드가 서로 같은 그래프에 속하는지 판별해주는 알고리즘

 

크루스칼 알고리즘에도 쓰이는 중요한 그래프 알고리즘

 

알고리즘 사례

위와 같이 모두 떨어져있는 집합 각각 6개씩 있다고 가정하자.

각각의 부모노드는 자기자신이다.

 

여기서 2와 3를 연결했다고 해보자. (이 때 i값이 작은쪽이 부모노드가 된다고 가정한다 보통 작은 쪽이 부모노드가 되는 게 일반적)

 

 

이제 1과 2를 연결해보자.

 

위의 표를 보면 알 수 있듯이 합집합으로 되어있는 노드들의 부모노드 값들이 전부 조상노드로 향하는 게 아니라는 걸 알 수 있다.

그렇기 때문에 합집합으로 다 연결을 했다고 해도 표값만으로 비교해서 두 노드가 합집합인지 아닌지 알 수 없다.

 

#include <bits/stdc++.h>
using namespace std;

int n, m;
int parent[1000001];

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

void unionVertex(int a, int b){

    a = find_parent(a);
    b = find_parent(b);

    if(a == b) return;
    else parent[a] = b;
    
}

int main(){
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m;

    for(int i=0;i<=n;i++) parent[i] = i; 

    int k, a, b;
    for(int i=0;i<m;i++){
        cin >> k >> a >> b;

        if(k == 0) {
            if(a == b) continue;
            if(a > b) swap(a, b);
            unionVertex(a, b);
        }
        else {
            if(find_parent(a) != find_parent(b)) cout << "NO\n";
            else cout << "YES\n";
        }
    }
}

위의 소스 코드는 unionfind 기본 문제의 소스 코드이다.

 

if(find_parent(a) != find_parent(b))

 

위의 문제처럼 두 노드가 합집합인지 아닌지 판별할 때는 find_parent함수를 이용해 그 조상노드가 어떤 노드인지 확인을 한 후 판별을 꼭 해야한다.

 

void unionVertex(int a, int b){

    a = find_parent(a);
    b = find_parent(b);

    if(a == b) return;
    else parent[a] = b;
    
}

 

두 노드가 속한 집합들을 합칠 때 쓰는 함수이다.

두 노드의 조상을 찾고 서로 같다면 이미 같은 합집합이고, 아니라면 한쪽이 다른 한쪽의 부모노드가 된다.

 

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

 

해당 노드의 조상 노드를 찾는 함수이다.

노드의 부모노드와 자기자신이 같다면 자기자신을 리턴해주고, 같지 않다면 그 부모노드의 부모노드를 재귀형식으로 계속 구해준다. 이 때, 

 

parent[x] = find_parent(parent[x]);

 

이런 식으로 기록을 해주어야 시간을 아낄 수 있다.

 

아래의 문제는 union-find 문제들의 풀이이다.

 

https://kimmessi.tistory.com/225

https://kimmessi.tistory.com/226