[Union find] c++ 구현 및 설명

목차

 

Union find (분리 집합) 정의

서로소 집합이라고 불리며 공통 원소를 가지지 않는 집합을 말한다.

예를 들면 1그룹과 2그룹이 있을 때 관계의 확인을 위해 일일히 bfs, dfs를 돌리는 것은 비효율적이므로

자기 그룹의 꼭대기에 있는 사람만 비교하는 것이다.

 

2와 8은 다른 그룹인 것을 알 수 있다.

 

 

 

트리에 값 추가하는 방법

parent[2] = 3;
parent[7] = 3;
parent[5] = 3;
parent[8] = 4;

 

 

 

 

두 수가 같은 집합인지 알기 위해 필요한 함수

int find_root(int node) {

	if (parent[node].first == node)
		return node;
		//노드의 최적화: 항상 부모를 루트노드로 만듬

	return parent[node] = find_root(parent[node]);

}

 

 

그러면 여기서 의문이 든다

왜 parent[node]를 반환하지 않고 parent[node] = find_root(parent[node])를 반환했는가

이는 탐색의 효율성을 위해서이다. 바로 자식 노드를 루트 노드에 연결하여 순차적 탐색을 막아준다.

 

 

 

 

두 트리를 이어주는 함수

void union_root(int x, int y) {
    //x, y 정점의 최상위 정점을 각각 찾는다. (속한 트리의 루트 노드를 찾는다.)
    x = find_root(x);
    y = find_root(y);
 
    if (x != y) {
        //서로 다른 트리에 속한다면, 한 쪽의 트리를 다른 쪽에 붙인다.
        //***항상 높이가 낮은 트리를 높이가 높은 트리에 붙인다.***
        if (node_rank[x] < node_rank[y]) parent[x] = y;
        else parent[y] = x;
 
        //만약 합친 두 트리의 높이가 같다면, 합친 후 트리의 높이를 1 증가시킨다.
        if (node_rank[x] == node_rank[y]) {
            parent[x] = y;
            node_rank[x]++;
        }
    }
}

 

높이가 낮은 트리를 높은 트리에 붙여야 하는 이유는 높이를 일정하게 유지하여 탐색의 효율을 높일 수 있다.

 

 

• 높이가 낮은 트리를 높은 트리에 붙인 경우 -> 높이: 3

 

 

 

• 높이가 높은 트리를 낮은 트리에 붙인 경우 -> 높이: 4

 

 

• 높이가 같은 트리일 경우 -> 높이: 기존 높이+1

 

참고

https://4legs-study.tistory.com/94?category=886581

분리 집합 (Disjoint Set) : Union-Find