[数据结构]并查集(系统整理版)
基础用法
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-basediota(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[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-basediota(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[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-basediota(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[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();}
};