union find

분리 집합, 서로소 집합, 유니온 파인드

참고

Disjoint set은 서로 중복되지 않는 부분 집합들로 나누어진 원소들에 대한 정보를 저장하고 조작하는 자료구조이다.

연관 문제

• 백준.1043.거짓말
• 백준.1717.집합의 표현

시간 복잡도

find(x)

• 트리의 높이와 시간 복잡도가 동일하다.
• 최악의 경우 O(N - 1)이다.

union(x, y)

• find 연산이 전체 수행시간을 지배한다.
• 즉, 최악의 경우 O(N - 1)이다.

union의 경우 O(a(N)) 이고, a는 애커만 상수이다. 따라서 거의 상수라고 봐도 무방하다.

구현

c언어에서 union을 예약어로 사용하고 있음에 주의한다.

struct DisjointSet {
  vector<int> parents;
  vector<int> counts;

  DisjointSet(int size) {
    parents.resize(size);
    counts.resize(size);

    for (int i = 0; i < size; i++) {
      parents[i] = i;
      counts[i] = 1;
    }
  }

  int findNode(int node) {
    if (parents[node] == node) return node;

    return parents[node] = findNode(parents[node]);
  }

  bool isLinked(int nodeA, int nodeB) {
    return findNode(nodeA) == findNode(nodeB);
  }

  void merge(int nodeA, int nodeB) {
    if (nodeA > nodeB) swap(nodeA, nodeB);

    nodeA = findNode(nodeA);
    nodeB = findNode(nodeB);

    if (nodeA == nodeB) return;
    if (counts[nodeA] < counts[nodeB]) swap(nodeA, nodeB);

    parents[nodeB] = nodeA;
    if (counts[nodeA] == counts[nodeB]) counts[nodeB]++;
  }
};