ユニオン并查集

Union Find is a data structure that keeps track of elements which are split into one or more disjoint sets.

#define MAX 10000
struct Node
{
    int data;       // 该元素保存的数据
    int rank;       // 以该元素为root形成的子树的高度
    int parent; // parent node
 }node[MAX];

int set[max];//集合index的类别，或者用parent表示
int rank[max];//集合index的层次，通常初始化为0
int data[max];//集合index的数据

//初始化集合
void Make_Set(int i)
{
    set[i]=i;//初始化的时候，一个集合的parent都是这个集合自己的标号。没有跟它同类的集合，那么这个集合的源头只能是自己了。
    rank[i]=0;
}

  # to unify two elements, first find their roots
  root1 = root of e1
  root2 = root of e2

  # if roots are different, let one be the parent of the other
  if root1 == root2:
    return
  else:
    parent[root1] = root2 / parent[root2] = root1