[Algorithm] # Union - Find

Union-Find란

이번 시간에는 union-find 알고리즘을 간단히 정리해보려 합니다.

• union(x, y) 연산은 x와 y 요소의 서로 다른 두 집합을 합친 합집합을 만듭니다.
• find(x) 연산은 x가 속해있는 집합을 반환하는 연산입니다.

예들 들어, S = { 1, 2, 3, 4, 5 } 집합이 있다고 가정하고 초기에 각 원소는 다른 집합에 속해 있다고 가정하겠습니다.

{1} {2} {3} {4} {5}

union(1, 2) union(3, 4) 연산을 수행하면 아래 결과를 반환합니다.

{1, 2} {3, 4} {5}

다시 한번, union(1, 4) 연산을 수행합니다.

{1, 2, 3, 4} {5}

이렇게 각 요소가 속한 집합을 찾고, 합치는 연산을 바로 Union-Find 알고리즘이라 합니다.

구현

이번에 kruskal 알고리즘을 공부하면서 Union-Find 알고리즘을 구현해봤습니다.

int set_find(int curr) {
  if (parent[curr] == -1) {
    return curr;
  }
  while(parent[curr] != -1) {
    curr = parent[curr];
  }
  return curr;
}

void set_union(int a, int b) {
  int root1 = set_find(a);
  int root2 = set_find(b);

  if (root1 != root2) {
    parent[root1] = root2;
  }
}