c++ 并查集实现优化

定义
并查集(Disjoint-Set)是一种可以动态维护若干个不重叠的集合，并支持合并与查询两种操作的一种数据结构

并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。常常在使用中以森林来表示。

并查集有两个基本操作：

Find: 查找元素所属子集
Union：合并两个子集为一个新的集合

并查集的基本结构

我们可以使用树这种数据结构来表示集合，不同的树就是不同的集合，并查集中包含了多棵树，表示并查集中不同的子集，树的集合是森林，所以并查集属于森林。
若集合S={0, 1, 2, 3, 4, 5, 6}，最初每一个元素都是一棵树。

实现
我们建立一个数组fa[ ]表示一个并查集，fa[i]表示i的父节点。

初始化：把每个点所在集合初始化为其自身fa[i] = i。通常来说，这个步骤在每次使用该数据结构时只需要执行一次，无论何种实现方式，时间复杂度均为O(N)。
查找查找元素所在的集合。即每一个节点不断寻找自己的父节点，若此时自己的父节点就是自己，那么该点为集合的根结点，返回该点。复杂度为O(D), D为节点的深度(或者到达父节点的路径长度)
合并将两个元素所在的集合合并为一个集合。通常来说，合并之前，应先判断两个元素是否属于同一集合，这可用上面的“查找”操作实现。fa[RootA]=RootB,其中RootA,RootB是两个元素的根结点

实现1 未优化

class UnionFind{
private:
    int* parent;
    
public:
    UnionFind(int maxsize):parent(new int[maxsize]){
        for(int i=0;i<maxsize;i++)
            parent[i] = i;
    }
    ~UnionFind(){
        delete[] parent;
    }

    int find(int p){
        if(parent[p] != p ) return find(parent[p]);
        return p;
    }
    
    bool isConnected(int a,int b){
        return find(a)==find(b);
    }

    void union_elem(int a,int b){
        int aroot = find(a);
        int broot = find(b);
        if(aroot!=broot) parent[aroot] = broot;
        else return;
    }
};

非递归 find

//得递归版本
  int find(int p){
  	while(parent[p] != p ) p = parent[p];
    return p;
  }

实现二优化

由于上面的实现对于树的形态没有做限制，所以树的合并 很容易出现严重不平衡的情况，如退化成深度很深的单分支树，查找的复杂度为O(H), H为树的高度。

优化目的: 为了限制元素合并后树的形态，从而使得查找(find)操作更高效

按元素合并
按秩合并
路径压缩

按秩合并
该方法使用秩表示当前树(节点)的高度，在合并时，总是将较小秩的树根指向具有较大秩的树根(通俗讲，就是总是将比较矮的树作为子树，添加到较高的树中。保持合并后高度较小)。为了保存秩，需要额外一个和parent相同长度的空间，初始化为0



class UnionFind2{
private:
    int* parent;
    int* rank;

public:
    UnionFind2(int maxsize):parent(new int[maxsize]),rank(new int[maxsize]){
        for(int i=0;i<maxsize;i++) {
            parent[i] = i;
            rank[i] = 0;
        }
    }

    ~UnionFind2(){
        delete[] parent;
        delete[] rank;
    }
    
	// 路径压缩
    int find(int p){
        if(parent[p] != p ) parent[p] = find(parent[p]);
        return p;
    }

    bool isConnected(int a,int b){
        return find(a)==find(b);
    }
    
	// 按秩合并
    void union_elem(int a,int b){
        int aroot = find(a);
        int broot = find(b);
        if(aroot!=broot) {
            if(rank[aroot] > rank[broot]){
                parent[broot] = aroot;
            }else if(rank[aroot] < rank[broot]) {
                parent[aroot] = broot;
            }
            else{
            // broot合并了aroot,broot秩 加1
                parent[aroot] = broot;
                rank[broot]+=1;
            }
        }
        else return;
    }
};

路径压缩
就是在每次查找时，令查找路径上的每个节点都直接指向根节点，如图所示。

实际上，我们在查询过程中只关心根结点是什么，并不关心这棵树的形态(有一些题除外)。因此我们可以在查询操作的时候将访问过的每个点都指向树根，这样的方法叫做路径压缩，单次操作复杂度为𝑂(𝑙𝑜𝑔𝑁)。

实现


// 递归版本
int find(int x) {
    if (x != uset[x]) uset[x] = find(uset[x]);
    return uset[x];
}

// 非递归版本
int find(int x) {
    int p = x, t;
    while (uset[p] != p) p = uset[p];
    while (x != p) { t = uset[x]; uset[x] = p; x = t; }
    return x;
}

c++ 并查集实现 优化

实现1 未优化

实现二 优化

c++ 并查集实现优化

实现二优化