https://twpower.github.io/115-union-find-disjoint-set
서로소 집합을 빠르게 병합하고, 같은 집합에 속한 요소들인지 아닌지를 빠르게 판별할 수 있는 자료구조.
배열로 구현 가능.
각 배열에는 각 집합의 대표자를 저장한다.
크게 두개의 함수를 필요로 한다.
int Find(a) 함수 : a가 속한 집합의 대표자를 구하는 함수. 재귀를 통해 대표자를 구하고, uf[a] 도 그 대표자로 수정하면 된다. 최종 대표자는 uf[T] == T 를 만족한다.
Union(a,b) 함수 : a와 b 가 서로 다른 집합에 속해있다면, b의 대표자의 대표를 a의 대표자로 변경하는것 만으로 두 집합을 병합할 수 있다. wow!
최단 스패닝트리를 구하는 크루스칼 알고리즘에서 유용하게 쓰인다.
'Algorithem' 카테고리의 다른 글
| 최장 증가 부분 수열 (LIS) : 수열 길이마다 최대값 갱신 (0) | 2023.01.05 |
|---|---|
| 거대한 피보나치 수열 : 행렬 곱으로 표현하기 (0) | 2023.01.05 |
| n, m 수열 만들기 (0) | 2023.01.05 |
| 순열 찾기 (python code) (0) | 2023.01.05 |
| 알고리즘의 이해 (0) | 2023.01.05 |
