基础用法

int p[N];

//路径压缩 寻找祖宗节点
int find(int x){
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}

int main(){
//初始化
    for(int i=1;i<=n;i++) p[i]=i;
}

合并

void merge(int a,int b){
    int aa=find(a),bb=find(bb);
    if(aa!=bb){
        p[aa]=bb;
    }
}

查询是否联通

bool is_connected(int a,int b){
    int aa=find(a),bb=find(bb);
    if(aa==bb) return 1;
    else return 0;
}

如何维护联通块数量

初始化cnt为元素个数n
每次合并时 cnt–
最后cnt即为最后的连通块个数

int cnt=n;
void merge(int a,int b){
    int aa=find(a),bb=find(bb);
    if(aa!=bb){
        p[aa]=bb;
    }
    cnt--;
}

如何维护每个连通块的元素个数

维护一个size数组s 初始化为1
for(int i=1;i<=n;i++) s[i]=1;

• size数组不能定义为int size[N]size会与cpp内部的关键字混淆

int s[N];
int cnt=n;

void merge(int u,int v){
    int uu=find(u),vv=find(v);
    if(uu!=vv){
        if(s[uu]>s[vv]){
            p[vv]=uu;
            s[uu]+=s[vv];
        }else{
            p[uu]=vv;
            s[vv]+=s[uu];
        }
        cnt--;
    }
}

按秩合并

每次合并把元素少的连通块合并到元素多的去
因为并查集类似树形结构
这样合并能时树的高度增长相对少
减少路径压缩次数 提高查询效率

如何像STL一样使用并查集

借鉴了LeetCode的并查集模板

基础版

#include<bits/stdc++.h>
using namespace std;


class UnionFind{
private:
    vector<int>p,s;
public:
    int cnt=0;
    UnionFind(int n): p(n+1),s(n+1,1){//多开一个空间 同时适用于0-based&1-based
        iota(p.begin(),p.end(),0);
        cnt=n;
    }

    int find(int x){
        if(p[x]!=x) p[x]=find(p[x]);
        return p[x];
    }

    void merge(int u,int v){
        int uu=find(u),vv=find(v);
        if(uu!=vv){
            if(s[uu]>s[vv]){
                p[vv]=uu;
                s[uu]+=s[vv];
                roots.erase(vv);
            }else {
                p[uu]=vv;
                s[vv]+=s[uu];
                roots.erase(uu);
            }
            cnt--;
        }
    }
    
	bool is_connected(int u,int v){
        return find(u)==find(v);
    }
    
    int size(int x){
        return s[find(x)];
    }	

};

维护每个连通块的根节点

不需要维护cnt了 根节点的数量就是连通块的数量

#include<bits/stdc++.h>
using namespace std;

class UnionFind{
private:
    vector<int>p,s;
    unordered_set<int>roots;//新增
public:
    UnionFind(int n): p(n+1),s(n+1,1){//多开一个空间 同时适用于0-based&1-based
        iota(p.begin(),p.end(),0);
        for(int i=0;i<n;i++){//如果1-based就改成i->[1,n]
        	roots.insert(i);
        }
    }

    int find(int x){
        if(p[x]!=x) p[x]=find(p[x]);
        return p[x];
    }

    void merge(int u,int v){
        int uu=find(u),vv=find(v);
        if(uu!=vv){
            if(s[uu]>s[vv]){
                p[vv]=uu;
                s[uu]+=s[vv];
                roots.erase(vv);
            }else {
                p[uu]=vv;
                s[vv]+=s[uu];
                roots.erase(uu);
            }
        }
    }
    
	bool is_connected(int u,int v){
        return find(u)==find(v);
    }
    
    int size(int x){
        return s[find(x)];
    }	
    
    vector<int>get_roots(){
		return vector<int>(roots.begin(),roots.end());
	}
	
	int get_cnt(){
		return roots.size();
	}
};

维护每个连通块内的边的数量

#include<bits/stdc++.h>
using namespace std;


class UnionFind{
private:
    vector<int>p,s,ecnt;//ecnt[i]表示以find(i)为根的连通块的边数
    unordered_set<int>roots;
public:
    UnionFind(int n): p(n+1),s(n+1,1),ecnt(n+1,0){//多开一个空间 同时适用于0-based&1-based
        iota(p.begin(),p.end(),0);
        for(int i=0;i<n;i++){//如果1-based就改成i->[1,n]
        	roots.insert(i);
        }
    }

    int find(int x){
        if(p[x]!=x) p[x]=find(p[x]);
        return p[x];
    }

    void merge(int u,int v){
        int uu=find(u),vv=find(v);
        if(uu!=vv){
            if(s[uu]>s[vv]){
                p[vv]=uu;
                s[uu]+=s[vv];
                ecnt[uu]+=ecnt[vv]+1;
                roots.erase(vv);
            }else {
                p[uu]=vv;
                s[vv]+=s[uu];
                ecnt[vv]+=ecnt[uu]+1;
                roots.erase(uu);
            }
        }else{
			ecnt[uu]++;//已经联通了也要加边数
		}
    }
    
	bool is_connected(int u,int v){
        return find(u)==find(v);
    }
    
    int size(int x){
        return s[find(x)];
    }	

	int get_ecnt(int x){
		return ecnt[find(x)];
	}    

    vector<int>get_roots(){
		return vector<int>(roots.begin(),roots.end());
	}
	
	int get_cnt(){
		return roots.size();
	}
};

size函数里面必须返回s[find(x)]