Union-Find

  int init() {
      for (int i = 1; i <= N; i++)
          root[i] = i;
  }

  int find(int x) {
      return root[x] == x? x : find(root[x]);
  }
	
  // Path Compression : return되는 root 값을 이용하여 root 바로 밑으로 옮겨 경로를 압축하는 방법
  int find2(int x) {
      if (root[x] == x) return x;
      return root[x] = find(root[x]);
  }

  // union이 keyword이기 때문에 함수명을 merge로 명명
  void merge(int x, int y) { 
      x = find(x);
      y = find(y);
		
      root[y] = x;
  }

  // subtree x와 y의 높이(rank)를 비교하여 낮은 높이의 트리가 높은 트리의 하위로 합쳐진다
  // Path Compression이 적용된 find2()를 사용하면 rank가 실제 트리의 높이를 의미하지 않게 될 수 있다
  // 하지만, Path Compression과 rank를 같이 쓸 수는 있고, 조금이나마 최적화가 될 수 있다
  // 깊이(depth)나 높이(height)를 쓰지 않고 rank를 쓰는 이유는 
  // Path Compression을 통해 실제 트리의 높이를 의미하지 않게 될 수 있기 때문이다
  void merge2(int x, int y) { 
      x = find(x);
      y = find(y);
			
      if (x == y) return;
      if (rank[x] < rank[y])
          root[x] = y;
      else {
          root[y] = x;
          if (rank[x] == rank[y])
              rank[x]++;
      }
  }

  // 집합의 원소 개수를 계산한다
  int merge3(int x, int y) { 
      x = find(x);
      y = find(y);
		
      if (x != y) {
          root[x] = y;
          nodeCnt[x] += nodeCnt[y];
          nodeCnt[y] = 1;
      }
      return nodeCnt[x];
  }