[Algorithm] Union find

Disjoint set

• 서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장, 조작하는 자료구조
• 서로소 집합 자료구조

Union find

• Disjoint set을 표현할 때 사용하는 알고리즘
• 주로 트리 구조를 이용하여 구현

Process of operation

• initialization
  • 모든 원소가 자기 자신을 부모로 가리키는 집합 구성
• getParent
  • 해당 원소가 가리키는 부모를 반환 (어떤 집합에 있는지 확인)
• unionParent
  • 서로 다른 집합이 같은 원소를 포함하고 있다면 합치기
  • 합치는 과정은 가리키는 부모를 통일 시키는 것
  • 주로 낮은 수를 우선순위로 두어 부모로 통일

// initialization
for (int i = 0; i <= n; ++i) {
    parent[i] = i;
}

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

// unionParent
void unionParent(int a, int b) {
	a = getParent(a);
	b = getParent(b);
	if (a < b) parent[b] = a;
	else parent[a] = b;
}

백준 예제 문제집

---

ref :
Union-Find 알고리즘