数据结构与算法分析 – Disjoint Set（并查集）

什么是并查集？
并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。

并查集的主要操作
1.合并两个不相交集合
2.判断两个元素是否属于同一集合

主要操作的解释及代码
一开始我们假设元素都是分别属于一个独立的集合里的。
(1).合并两个不相交集合 操作很简单：先设置一个数组Father[x]，表示x的“父亲”的编号。 那么，合并两个不相交集合的方法就是，找到其中一个集合最父亲的父亲（也就是最久远的祖先），将另外一个集合的最久远的祖先的父亲指向它。

上图为两个不相交集合，b图为合并后id(b)=id(g)

   1:  void init()

   2:  {

   3:      for (int i=0; i<N; i++)

   4:          id[i] = -1;

   5:  }

   6:   

   7:  void union(int x, int y)

   8:  {

   9:     id[find_root(x)]=find_root(y)

  10:  }

(2).判断两个元素是否属于同一集合仍然使用上面的数组,则本操作即可转换为寻找两个元素的最久远祖先是否相同。可以采用递归实现。

   1:  bool judge(int x, int y)

   2:  {

   3:      return find_root(x) == find_root(y);

   4:  }

并查集的优化
(1).路径压缩
刚才我们说过，寻找祖先时采用递归，但是一旦元素一多起来，或退化成一条链，每次GetFather都将会使用O（n）的复杂度，这显然不是我们想要的。
对此，我们必须要进行路径压缩，即我们找到最久远的祖先时“顺便”把它的子孙直接连接到它上面,这就是路径压缩了。

   1:  int find_root(int n)

   2:  {

   3:      if (id[n] != -1)

   4:          id[n] = find_root(id[n]);

   5:      return id[n];

   6:  }

(2).rank合并
1.按照树的高度合并。

   1:  int rank[N]={0};// 节点高度的上界 

   2:   

   3:  void union(int x, int y)

   4:  {

   5:      int rx=find_root(x);

   6:      int ry=find_root(y);

   7:      if (rank[rx] > rank[ry])

   8:          id[ry] = rx;

   9:     else {

  10:          id[rx] = ry;

  11:          if (rank[rx] == rank[ry])

  12:              rank[ry]++;

  13:      }

  14:  }

2.按照集合的大小合并

   1:  int rank[N];// 集合的大小

   2:   

   3:  void init(){

   4:  for(int i=0;i<N;i++){

   5:      id[i]=-1;

   6:      rank[i]=1;

   7:  }

   8:  void union(int x, int y)

   9:  {

  10:      int rx=find_root(x);

  11:      int ry=find_root(y);

  12:      if (rank[rx] > rank[ry]){

  13:          rank[rx]+=rank[ry];

  14:          id[ry] = rx;

  15:      }

  16:     else {

  17:          rank[ry]+=rank[rx];

  18:          id[rx] = ry;

  19:      }

  20:  }

数据结构与算法分析 – Disjoint Set（并查集）

原文：http://www.cnblogs.com/ZJUT-jiangnan/p/3561766.html