“서로소 집합”이라고도 한다.
전체 집합 U에 대하여, U의 분리 집합 A와 B는 아래 조건을 만족한다.
다시 한 번 정리하자면, 전체 집합 U의 모든 원소 U의 부분 집합 A, B 둘 중 하나에는 반드시 속하면서, 둘에 동시에 속하진 않는 경우, A, B는 U의 분리 집합이다.
즉, U를 완전히 분리(disjoint)하는 구분선이나 경계같은게 있어서, 그것으로 구분되는 두 집합이라고 볼 수 있다.
저 분리 집합을 구현하기 위한 알고리즘이 바로 Union - Find 알고리즘이다. 각 노드마다 그 노드의 부모 노드의 번호를 기록하여, 그룹을 분리하고 트리로 표현한다.
노드들을 트리로 표현하였기 때문에 항상 root노드를 가지게 되고, root 노드의 종류가 다르기 떄문에 그룹을 구분할 수 있게 된다. (이 때 root 노드의 부모 노드는 자기 자신.) 즉 그룹의 대표를 세움으로서 그룹을 구분한다고 볼 수 있다.
임의의 노드들의 root를 비교하여 각 노드들이 같은 그룹에 속해있는지 아닌지 알 수 있다.
Union-Find 알고리즘의 구현은 “Union”과 “Find”라는 연산의 정의와 구현으로 이루어진다. 그리고 좀 웃기게도 이름은 Union - Find 알고리즘인데, 일반적으로는 Find를 먼저 구현해야 Union을 구현할 수 있다.
일반적으로는 각 노드 번호가 index에 대응하는 1차원 배열에 각 노드의 parent노드를 저장하는 식으로 구현한다.
root노드를 찾는 작업. root가 자신이 아닐 때 까지 부모노드를 방문하면 된다.
이 때, 단순 연결관계가 길게 이어져있는 경우 비효율적인 연쇄 방문이 일어날 수 있다. Find연산으로 root노드를 찾은 경우, 해당 노드의 parent를 root노드로 바꾸어 트리가 담고있는 분리집합 정보 자체는 변하지 않는다.