模板1：

这里也可以应用一个简单的启发式策略——按秩合并。该方法使用秩来表示树高度的上界，在合并时，总是将具有较小秩的树根指向具有较大秩的树根。简单的说，就是总是将比较矮的树作为子树，添加到较高的树中。简单的说，就是总是将比较矮的树作为子树，添加到较高的树中。为了保存秩，需要额外使用一个与 parent 同长度的数组，并将所有元素都初始化为 0。

1 const int maxn=505; 2 int parent[maxn],rank_[maxn]; 3 //构造并查集 4 void p(int n) 5 { 6     for(int i=0;i
     
      rank_[y])24         parent[y]=x;25     else26     {27         parent[x]=y;28         if(rank_[x]==rank_[y])29             rank_[y]++;30     }31 }
     

 

模板2：

除了按秩合并，并查集还有一种常见的策略，就是按集合中包含的元素个数（或者说树中的节点数）合并，将包含节点较少的树根，指向包含节点较多的树根。这个策略与按秩合并的策略类似，同样可以提升并查集的运行速度，而且省去了额外的 rank_ 数组。

这样的并查集具有一个略微不同的定义，即若 parent 的值是正数，则表示该元素的父节点（的索引）；若是负数，则表示该元素是所在集合的代表（即树根），而且值的相反数即为集合中的元素个数。

如果要获取某个元素 x 所在集合包含的元素个数，可以使用 -parent[find(x)] 得到。

1 const int maxn=505; 2 int parent[maxn],rank_[maxn]; 3 void p(int n) 4 { 5     for(int i=0;i