유니온-파인드(분리 집합) 계산기

「이 둘이 같은 무리인가」를 아주 빠르게 답해야 할 때 씁니다. 원소마다 부모를 하나씩 두어 숲을 만들고 뿌리가 같으면 같은 무리로 보며, 합칠 때는 한쪽 뿌리를 다른 쪽 뿌리 밑에 붙입니다. 크루스칼 알고리즘에서 간선을 넣으면 사이클이 생기는지 판정하는 데 쓰이는 것이 대표적입니다.

최악의 경우 find 한 번이 O(n)이 됩니다. 최적화를 모두 끄고 union(0,1), union(1,2), union(2,3) …처럼 사슬로 이으면 부모가 한 줄로 늘어져 트리 높이가 원소 수 −1이 되기 때문입니다. 이 계산기의 「사슬로 잇기」 예제를 눌러 최적화를 끄면 그 모양을 그대로 볼 수 있습니다.

하나만 써도 크게 나아지지만 함께 쓸 때가 가장 좋습니다. 랭크 합치기만 쓰면 높이가 log₂n 아래로 눌리고, 경로 압축만 써도 한 번 훑은 길이 납작해집니다. 둘을 함께 쓰면 한 연산의 평균 비용이 역아커만 함수 α(n)에 비례해 현실의 어떤 n에서도 4를 넘지 않으며, 이것을 「거의 상수 시간」이라고 부릅니다.

정확히는 높이의 상한입니다. 경로 압축을 켜면 트리가 납작해지는데 랭크는 줄이지 않기 때문에, 압축 뒤의 랭크는 실제 높이보다 클 수 있습니다. 랭크를 줄이려면 트리 전체를 다시 살펴야 해서 이득보다 비용이 커지고, 상한으로 쓰는 데는 아무 문제가 없어 그대로 둡니다.

합치는 두 뿌리의 랭크가 같을 때뿐입니다. 랭크가 다르면 낮은 쪽을 높은 쪽 밑에 붙이므로 높이가 자라지 않고, 같을 때만 한쪽을 다른 쪽 밑에 붙이며 위쪽 랭크가 1 오릅니다. 랭크가 k인 트리를 만들려면 원소가 최소 2^k개 필요하다는 뜻이라, 여기서 높이가 log₂n 아래로 눌린다는 성질이 나옵니다.

붙이는 방향의 규약이 다르기 때문입니다. 이 계산기는 랭크 합치기를 끈 경우 a 쪽 뿌리를 b 쪽 뿌리 밑에 붙이고, 랭크가 같을 때는 b 쪽을 a 쪽 밑에 붙이며 a 쪽 랭크를 올립니다. 교재에 따라 반대로 적기도 하지만, 어느 규약에서든 「같은 집합인가」의 답과 집합의 개수는 같습니다.

전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.