一、并查集-基础版
class UnionFind{ private: vector<int> parent; public: UnionFind(int n){ parent.resize(n); iota(parent.begin(),parent.end(),0); } int find(int index){//查找根节点 if(index==parent[index]) return index; parent[index]=find(parent[index]);//所有关联节点的父节点都指向关联的根节点 return parent[index]; } void unite(int index1,int index2){//关联（将第一个变量的根节点的父节点指向第二个变量的根节点） parent[find(index1)]=find(index2); } };
二、并查集-操作二维数组
只要将二维转化为一维即可比如n*n的矩阵
对于一个坐标为(x,y)的点，对应索引为x*n+y
class UnionFind{ private: vector<int> parent; public: UnionFind(int n){ parent.resize(n); iota(parent.begin(),parent.end(),0); } int find(int index){//查找根节点 if(index==parent[index]) return index; parent[index]=find(parent[index]);//所有关联节点的父节点都指向关联的根节点 return parent[index]; } void unite(int index1,int index2){//关联（将第一个变量的根节点的父节点指向第二个变量的根节点） parent[find(index1)]=find(index2); } }; int main(){ int m,n; cin>>m>>n; vector<vector<int>> mat(m,vector<int>(n)); //... UnionFind uf(m*n); }
三、并查集-获得集合数量
思路：不同的集合，每次合并，都会让集合数量-1
class UnionFind{ private: vector<int> parent; int setNum; public: UnionFind(int n){ parent.resize(n); iota(parent.begin(),parent.end(),0); setNum=n;//初始集合数量为n } int find(int index){ if(parent[index]==index) return index; parent[index]=find(parent[index]); return parent[index]; } void unite(int index1,int index2){ int p1=find(index1); int p2=find(index2); if(p1!=p2){//如果两个集合不是同一个，那么合并集合，集合数量减一 parent[p1]=p2; setNum--; } } int getSetNum(){ return setNum; } };
四、并查集-获得每个集合中元素的数量
每个元素的数量通过size数组，初始化为1（刚开始每个元素都是一个集合）。
我们只把数量保存在父节点上，也就是说size[find(index)]去获取当前index对应的集合数量
只要将子节点的数量全部转移给父节点就行了，然后子节点的数量置空。
通过getSize去获取对应index的集合的元素数量
class UnionFind{ public: vector<int> parent; vector<int> size; UnionFind(int n){ parent.resize(n*n); size.resize(n*n,1); iota(parent.begin(),parent.end(),0); } int find(int index){ if(index==parent[index]) return index; return parent[index]=find(parent[index]); } void unite(int index1,int index2){ int p1=find(index1),p2=find(index2); parent[p1]=p2; if(p1!=p2){//如果相等,会出现把size[p1]=size[p2]=0 都清空的异常情况 size[p2]+=size[p1]; size[p1]=0; } } int getSize(int index){ return size[find(index)]; } };
五、并查集+带权有向图
根本不同的应用场景，权重变化有着不同的传递方式。
下面以leetcode-399：除法求值为例
class UnionFind{ private: vector<int> parent; vector<double> weight; public: UnionFind(int n){ parent.resize(n); weight.resize(n); for(int i=0;i<n;i++){ parent[i]=i; weight[i]=1; } } int find(int index){ if(index==parent[index]) return index; int origin=parent[index]; parent[index]=find(parent[index]);//同时会把父节点的weight也更新好 weight[index]*=weight[origin]; return parent[index]; } void unite(int index1,int index2,double value){ int p1=find(index1); int p2=find(index2); if(p1!=p2){ parent[p1]=p2; weight[p1]=weight[index2]*value/weight[index1]; } } double isConnected(int index1,int index2){ int p1=find(index1); int p2=find(index2); if(p1==p2){ return weight[index1]/weight[index2]; } else return -1; } }; //......
