Disjoint-Set (서로소 집합)

Disjoint-Set (서로소 집합)

서로 중복되지 않는 부분 집합들 로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조

• 즉, 공통 원소가 없는 상호 배타적인 부분 집합들로 나눠진 원소들에 대한 자료구조이다.

Union-Find

Disjoint Set을 표현할 때 사용하는 알고리즘

Union-Find의 연산

• make-set(x)

  • 초기화
  • x를 유일한 원소로 하는 새로운 집합을 만든다.

  private static void makeSet(int n){
      parent = new int[n];
      for(int i = 1; i <= n; i++){
      parent[i] = i;
  }

• union(x, y)

  • 합하기
  • x가 속한 집합과 y가 속한 집합을 합친다. 즉, x와 y가 속한 두 집합을 합치는 연산

  private static void union(int x, int y) {
      x = find(x);
      y = find(y);
      if (x != y) {
          if (x < y)
              parent[y] = x;
          else
              parent[x] = y;
      }
  }

• find(x)

  • 찾기
  • x가 속한 집합의 대표값(루트 노드 값)을 반환한다. 즉, x가 어떤 집합에 속해 있는지 찾는 연산

  private static int find(int x) {
      if (x == parent[x])
          return x;
      else
          return parent[x] = find(parent[x]);
  }