Union find
Graph 에서 노드들을 그룹화 할 때 사용하는 알고리즘.
주의. union 시 순서를 지정하지 않고 저장할 경우 느리다.
java
int[] root;
public void initRoot() {
root = new int[numOfN + 1];
for (int i = 0; i < numOfN + 1; i++) {
root[i] = i;
}
}
public int find(int k) {
if (root[k] == k) {
return k;
} else {
return find(root[k]);
}
}
public void union(int a, int b) {
a = find(a);
b = find(b);
if (a != b) {
if (a < b) {
root[a] = b;
} else {
root[b] = a;
}
}
}
Java - without recursion
위의 경우에 recusion 때문에 성능이 떨어진다. find 를 loop 로 충분히 처리 가능하다.
for (;root[n1] != n1; n1 = root[n1]);
for (;root[n2] != n2; n2 = root[n2]);