CTDL Disjoint-set với rank heuristic

CẤU TRÚC DỮ LIỆU DISJOIN - SET

Ý nghĩa: cấu trúc dữ liệu Disjoin - set dùng để biểu diễn các tập hợp, mỗi tập hợp có thể có giá trị từ 0 đến n. Disjoin - set cho phép thực hiện nhanh các thao tác như: 
(1) Hợp 2 tập hợp thành một tập hợp
(2) Kiểm tra 2 phần tử có thuộc tập hợp không

Cấu trúc dữ liệu:

• Các phần tử: có giá trị từ 0, 1, 2, ..., n
• Các phần tử này thuộc tập hợp nào đó, nên ta quản lý tập hợp phần tử i thuộc là parent[i]. Như vậy một tập hợp là một cái cây, và gốc của cây là giá trị đại diện cho tập hợp

Như vậy, cấu disjoin set chỉ đơn giảng là một mảng parent[] của các phần tử i cho biết cha của phần tử i là ai.


Chương trình:
#include <bits/stdc++.h>
using namespace std;

const int maxn = 200000;

// Cấu trúc dữ liệu
int parent[maxn];
int n;

int rank[maxn];


void Init(int num) {
  n = num;
  fill(rank, rank + n, 0);
  for (int i = 0; i < n; i++) parent[i] = i;
}


int Root(int x) {
  return (x == parent[x]) ? x : (parent[x] = Root(parent[x]));
}


void UnionSet(int a, int b) {
  a = Root(a);
  b = Root(b);
  if (a == b) return;
  if (rank[a] < rank[b]) swap(a, b);
  if (rank[a] == rank[b]) ++rank[a];
  parent[b] = a;
}

bool IsSameSet(int a, int b) {
  a = Root(a);
  b = Root(b);

  return a==b;
}

int main() {
  Init(3);
  UnionSet(0, 2);
  cout << (0 == Root(0)) << '\n';
  cout << (1 == Root(1)) << '\n';
  cout << (0 == Root(2)) << '\n';
}