그림 13-12는 분리 집합을 보여 줍니다. 위에 있는 배열이 아래에 있는 트리를 표현한 것입니다. 그림에는 집합 {1, 2, 4}와 {0, 3} 두 개가 있습니다. 배열을 보면 {1, 2, 4} 집합의 루트인 2의 parent[i]=-1이 음수인 것을 알 수 있습니다. 다른 원소는 parent[i]가 자신의 부모를 나타냅니다. 예를 들어 parent[1]=2이므로 1의 부모는 2입니다. parent[3]=0은 3의 부모가 0임을 의미합니다. 여기서 FIND(i) 연산은 매개변수 i가 포함된 트리의 루트를 찾아 반환합니다. 예를 들어 FIND(1)=2입니다. UNION(i, j) 연산은 두 집합을 합치는 연산입니다. 매개변수 i, j는 반드시 루트여야 합니다.

그림으로 살펴볼까요? 그림 13-13은 UNION 연산을 보여 줍니다.

▲ 그림 13-13 분리 집합 2

그림 13-13에서 UNION(2, 0)을 실행하면 2의 부모를 0으로 만듭니다. parent[2]=0이면 집합은 {0, 1, 2, 3, 4}가 됩니다.