内容摘自维基百科
在计算机科学中，并查集是一种树型的数据结构，其保持着用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。有一个联合-查找算法（union-find algorithm）定义了两个操作用于此数据结构：
第一种方法，称为“按秩合并”，即总是将更小的树连接至更大的树上。因为影响运行时间的是树的深度，更小的树添加到更深的树的根上将不会增加秩除非它们的秩相同。在这个算法中，术语“秩”替代了“深度”，因为同时应用了路径压缩时（见下文）秩将不会与高度相同。单元素的树的秩定义为0，当两棵秩同为r的树联合时，它们的秩r+1。只使用这个方法将使最坏的运行时间提高至每个MakeSet、Union或Find操作
。
第二个优化，称为“路径压缩”，是一种在执行“查找”时扁平化树结构的方法。关键在于在路径上的每个节点都可以直接连接到根上；他们都有同样的表示方法。为了达到这样的效果，Find递归地经过树，改变每一个节点的引用到根节点。得到的树将更加扁平，为以后直接或者间接引用节点的操作加速。
int fa[N],Rank[N]; void Init(){ for(int i = 0; i < N; i++){ fa[i] = i; Rank[i] = 1; } } int getfather(int v){ ///带路径压缩的递归找根节点 if(fa[v] != v) fa[v] = getfather(fa[v]); return fa[v]; } void Union(int x, int y){ /// 普通合并操作 int fx = getfather(x); int fy = getfather(y); if(fx != fy) fa[fx] = fy; } bool Same(int x, int y){ ///判断是否同一集合； return getfather(x) == getfather(y); } void Weight_Union(int x, int y){///按秩合并，元素少的集合根节点指向元素多的集合的根节点； x = getfather(x); y = getfather(y); if(x == y) return ; if(Rank[x] >= Rank[y]){ fa[y] = x; Rank[x] += Rank[y]; }else{ fa[x] = y; Rank[y] += Rank[x]; } //cout<<x<<"\t"<<y<<"\t"<<Rank[x]<<"\t"<<Rank[y]<<endl; }
练习题目：
poj 1611：水题，敲完模板就能过；
原文：http://www.cnblogs.com/yoyo-sincerely/p/5191433.html