설명
집합 또는 그룹을 관리하기 위한 알고리즘이다. 각각의 그룹을 트리 구조로 관리한다. 이를 위해서는 각 노드마다 자신의 부모를 저장해야 한다. 이를 위해 각 노드의 부모를 저장하는 배열인 par를 만든다. 그러면 par[i]는 노드 i의 부모 노드가 된다.
disjoint set에서 수행하는 연산으로는 find, link가 있다.
find(x)
노드 x의 최고 조상을 return하는 함수이다.
자신이 최고 조상인 경우 자기 자신을 return하고, 아닌 경우 부모의 find 함수값을 return한다. 재귀적으로 함수를 호출하여 부모들을 통해 최고 조상으로 올라가는 것이다.
public static int find(int x) {
if (par[x] == x) return x; // par[x] == x이면 자신이 최고 조상인 것이다.
else return par[x] = find(par[x]);
}link(int x, int y)
노드 x가 속한 트리와, 노드 y가 속한 트리를 연결하는 함수이다. y의 최고 조상의 부모를 x의 최고 조상으로 설정하면 된다.
public static void link(int x, int y) {
par[find(y)] = find(x);
}