并查集

目的

1、 高效的解决点和点之间的连接问题,实例中就是网络中节点间的连接状态,这里的网络并不单单指代计算机网络,同时也指代现实中的关系网络.

2、 数学中的集合类实现,查询和并集合的操作.

连接问题和路径问题

前者只需要进行判断,后者有着更广阔的应用空间吗,无论是两者之间的最短路径还是具体的路径情况.

并查集

对于一组数据，支持两个动作

union(p,q) 合并两个集合

isConnected(p,q) 两个元素是否同属于一个集合

笔记内容

并查集的Rank[i]指的是根节点为i的树的高度.之所以不用height来形象的表示,是因为后面在路径压缩操作中,会将改变树的高度,这时候Rank值并不需要更新.是因为本身树高度的比较就是相对而言的,这时候Rank更多的意思是权重的意思.

代码实现

基础版本

# include <iostream>
class UF{
  public:
    UF(){}
    virtual bool isConnected(int p,int q)=0;
    virtual void unionElements(int p,int q)=0;
    virtual int getSize()=0;
    
    
};
class QuickUnionFind :public UF
{
    public:
        QuickUnionFind(int size)
        {
           id.resize(size);
           for(int i=0;i<id.size();i++)
           {
            id[i]=i;
           }
        
        }
        bool isConnected(int p,int q)
        {
        return find(p)==find(q);
        
        }
        void unionElements(int p,int q)
        {
        int pID=find(p);
        int qID=find(q);
        if(qID==pID)
            return;
        for(int i=0;i<id.size();i++)
        {
        if(id[i]==pID)
            id[i]=qID;
        }
        
        }
       inline int getSize(){return id.size();}
    private:
        int find(int p)
        {
         if(p<0||p>=id.size())
            return -1;
        return id[p];
    
        }
    private:
        vector<int> id;
};

增加了Rank和路径压缩

class UnionFind :public UF
{
    public:
            UnionFind(int size)
            {
            parent.resize(size);
            rank.resize(size);
            for(int i=0;i<size;i++)
            {
            parent[i]=i;
            rank[i]=1;
            }
                
            
            }
           inline int getSize(){return parent.size();}
           int find(int p)
           {
            if(p<0||p>=getSize())
                return -1;
            if(p!=parent[p])
            {
                parent[p]=find(parent[p]);   //进行路径压缩  使树的深度为2             
            }
            return parent[p];
           }
           bool isConnected(int p,int q)
           {
           return find(p)==find(q);
           }
           void unionElements(int p,int q)
           {
            int pRoot = find(p);
            int qRoot = find(q);
            if(pRoot==qRoot)
                return ;
         //根据两个元素所在的rank不同判断合并方向
           //将rank低的集合合并到rank高的集合上
            if(rank[pRoot]<rank[qRoot])
            {
                parent[pRoot]=qRoot;
            }
            else if(rank[qRoot]<rank[pRoot])
            {
                parent[qRoot]=pRoot;
            }else
            {
                  parent[pRoot]=qRoot;
                  rank[qRoot]++;
            }
           }
    private:
        vector<int> parent;
        vector<int> rank; //存储以i为为根的树的权重
};