常用类之四---并查集(Union-Find Sets)

并查集为解决等价类问题提供了一个高效快速的数据结构,在许多涉及到等价类的算法中,他都扮演着
改进算法中使用的数据机构的角色,他对提高算法的效率是可见一斑,例如在带有限期的作业问题中,在求最小生成树Kruskal算法都可以使用并查集高效的实现.

const int DefaultSize = 20;

class UFSets{
public:
 UFSets(int s = DefaultSize);
 ~UFSets();
 void Union(int root1,int root2);
 void WeightUnion(int root1,int root2);//基于加权规则的合并操作
                                       //使合并树保持较小的深度
                                       //减小Find的时间
 int Find(int x);//查找x元素的集合，并返回集合的名
 int  CollapsingFind(int x);//查找的过程中基于折叠规则进行路径压缩
private:
 int *parent;
 int size;
};
UFSets::UFSets(int s){
 size = s;
 parents = new int[size+1];
 for(int i= 0; i<= size; i++)
  parent[i] = -1;
}

int UFSets::Find(int x){
 if(parent[x] < 0) 
  return x;
 else 
  return Find(parent[x]);
}

void UFSets::Union(int root1,int root2){
 parent[root2] = root1;
}

void UFSets::WeightUnion(int root1,int root2){
 int weight = parent[root1] + parent[root2];
 if(parent[root1] < parent[root2]){
   parent[root1] = root2;
   parent[root2] = temp;
 }
 else{
   parent[root2] = root1;
   parent[root1] = temp;
 }
}

int UFSets::CollapsingFind(int x){
   int temp;
   for(int j = x; parent[j] >= 0; j = parent[j]);//查找x的根
   while(x != j){//把x所在的一支的节点依次连到根节点，使得树的深度
     temp = parent[x];//保持很小
  parent[x] = j;
  x = temp;
   }
}