대표 원소로 소속을 확인한다
Find(x)는 x가 속한 집합의 대표를 찾는다. 두 원소의 대표가 같으면 같은 집합에 속한다. 대표는 소속을 식별하기 위한 표지이며 반드시 집합에서 가장 작거나 큰 값일 필요는 없다.
집합을 합친다
처음 {A},{B},{C}로 나누어 놓고 Union(A,B)를 하면 {A,B},{C}가 된다. 이후 A와 B의 Find 결과는 같은 대표를 가리킨다. 같은 집합의 두 원소를 다시 합쳐도 분할은 달라지지 않는다.
트리로 구현한다
각 원소가 부모를 가리키게 하고 루트가 집합 대표가 되도록 구현할 수 있다. Find는 부모를 따라 루트를 찾고 Union은 서로 다른 두 루트를 연결한다. 아무 기준 없이 합치면 긴 사슬이 되어 탐색이 느려질 수 있다.
그래프에서의 활용
무향 그래프의 간선 양 끝을 차례로 합치면 연결 성분을 관리할 수 있다. 크루스칼 알고리즘에서는 두 정점이 이미 같은 성분인지 확인해 순환을 만드는 간선을 건너뛰는 데 쓴다. 기본 구조는 합치기에 적합하며 임의의 집합 분리를 같은 방식으로 지원하지는 않는다.
관련 문서
집합의 분할 / 연결 성분 / 크루스칼 알고리즘 / 트리 (그래프 이론) / 경로 압축 / 무향 그래프 / 집합