并查集 ¶

约 575 个字 233 行代码预计阅读时间 5 分钟

算法基础–并查集（含路径压缩，按秩合并，删除操作）并查集（按秩合并 + 路径压缩）基础讲解 +0 同学 luogu 博客

基础知识 ¶

1. 并查集的存储 ¶

使用一个数组fa[]保存父节点（father）//是不是很形象 按照题目要求开数组大小

int fa[SIZE];

2. 并查集的初始化 ¶

把每个节点的父亲设置为他自己

for(int i = 1; i <= n; i++){
 fa[i] = i;//爸爸是自己~
}

3. find（get）找祖宗函数 ¶

简短 version

int find(int x){
 return fa[x] == x ? fa[x] : (fa[x] = find(fa[x])); //路径压缩
}

稍微长一点

int find(int x){   //找爸爸函数 
 if(fa[x] != x) fa[x] = find(fa[x]);
 return fa[x];
}

4. merge 函数 ¶

路径压缩

均摊复杂度：\(O(\log N)\) 说的是每次查询时，都把访问过的每个节点，（查询元素的所有祖先）都直接指向树根

按秩合并

均摊复杂度：\(O(\log N)\) 把较小的树根作为较大的树根的子节点

同时运用路径压缩和按秩合并优化的并查集，每次find()时间复杂度降到了 \(O( α \left (\N\right))\) ,

其中 \(α \left (\N\right)\) 是反阿克曼函数，增长速率贼慢贼慢，相当与一个常数由 R.E.Tarjan 1975 年发表的论文给予了证明

题目选讲 ¶

01 P1551 亲戚 ¶

P1551 亲戚

路径压缩

#include<bits/stdc++.h>
using namespace std;
#define maxn 5000
int fa[maxn];
int n,m,p,x,y;
int find(int x){   //找爸爸函数 
 if(fa[x] != x) fa[x] = find(fa[x]);
 return fa[x];
}
int main(){
 cin>>n>>m>>p;
 for(int i = 1; i <= n;i++){
  fa[i] = i;
 }
 for(int i = 1; i <= m;i++){
  cin>>x>>y;
  fa[find(x)] = find(y);
 }
 for(int i = 1,; i <= p;i++){
  cin>>x>>y;
  if(find(x) == find(y)) printf("Yes\n");
  else      printf("No\n");
 }
 return 0;
}

按秩合并

#include<bits/stdc++.h>
using namespace std;
#define maxn 5000
int fa[maxn];
int rank[maxn];//深度数组 
int n,m,p;
int find(int x){  //找祖宗 函数 
 //if(fa[x] != x) fa[x] = find(fa[x]);//下面这句变成这句就变成了按秩合并 + 路径压缩
 if(fa[x] != x) find(fa[x]);
 //如果没找到祖宗，就一直找，最终 fa[x] = 他的祖宗 ; 
 return fa[x];//找到祖宗啦，返回值 
}
void work(int x,int y){   //按秩合并 
 if(x == y) return;
 if(rank[x] > rank[y]) fa[y] = x;//左边的树比右边的大（至少大 1 的情况 
 else{
  if(rank[x] == rank[y]) rank[y]++;//深度相等的话，两个合并深度肯定加一 
  fa[x] = y;     //合并，(拜师傅 
 }  
} 

int main(){
 cin>>n>>m>>p;
 for(int i = 1; i <= n;i++){ //初始化 
  fa[i] = i;    //每个人的祖宗都是他自己 
//  rank[i] = 0;   //深度初始化为一样的数；（有没有都可以这一步 
 }
 int x,y;
 for(int i = 1; i <= m;i++){
  cin>>x>>y;
  if(find(x)!=find(y))//合并是要把祖宗为首的树合并 
   work(find(x),find(y)); //所以参数是祖宗 
 }
 for(int i = 1,x = 0,y = 0; i <= p;i++){
  cin>>x>>y;
  if(find(x) == find(y)) printf("Yes\n");
  else      printf("No\n");
 }
 return 0;
}

02 P3367 模板 - 并查集 ¶

P3367 模板 - 并查集

//按秩合并 
#include<bits/stdc++.h>
using namespace std;
#define maxn 22000
int fa[maxn];
int r[maxn];//深度数组 
int n,m,p;
int find(int x){  //找祖宗 函数 
 if(fa[x] != x) fa[x] = find(fa[x]);
 //如果没找到祖宗，就一直找，最终 fa[x] = 他的祖宗 ; 
 return fa[x];//找到祖宗啦，返回值 
}
void work(int x,int y){   //按秩合并 
 if(x == y) return;
 if(r[x] > r[y]) fa[y] = x;//左边的树比右边的大（至少大 1 的情况 
 else{
  if(r[x] == r[y]) r[y]++;//深度相等的话，两个合并深度肯定加一 
  fa[x] = y;     //合并，(拜师傅 
 }  
} 

int main(){
 cin>>n>>m;
 for(int i = 1; i <= n;i++){ //初始化 
  fa[i] = i;    //每个人的祖宗都是他自己 
//  rank[i] = 0;   //深度初始化为一样的数；（有没有都可以这一步 
 }
 int x,y;
 for(int i = 1,z; i <= m;i++){
  cin>>z>>x>>y;
        if(z  ==  1){
            if(find(x)!=find(y))//合并是要把祖宗为首的树合并 
       work(find(x),find(y)); //所以参数是祖宗 
        }
        if(z  ==  2){
            if(find(x) == find(y)) printf("Y\n");
      else      printf("N\n");
        }
 }
 return 0;
}

03 P2024 [NOI2001] 食物链 ¶

P2024 [NOI2001] 食物链这道题和板子题略微有些不同需要考虑的问题是：如何使用并查集呢？

我们暂且把食物链 == 分为三类 ==，第一类是==自己==，第二类是它的==天敌==，第三类是它的==猎物== 所以我们每当知道一对关系，就把他们对应的三个情况更新一遍

我们实现的方法是开一个 3 倍的数组来存并查集关系

int fa[maxn*3];

把相同类别的并起来 ~

merge(x  , y);
merge(x+n , y+n);
merge(x+2*n , y+2*n);//合并关系

merge(x+n  , y);
merge(x+2*n , y+n);
merge(x  , y+2*n);//合并关系

AC code

#include<bits/stdc++.h>
using namespace std;
#define maxn 60000
int fa[maxn*3],r[maxn*3];
int n,m,t,x,y,cnt;
int find(int x){
 return fa[x] == x? fa[x] : (fa[x] = find(fa[x]));
}
void merge(int x,int y){
 int xx,yy; 
 xx = find(x),yy = find(y); 
 if(fa[xx] == fa[yy]) return ;
 if(r[xx] > r[yy]){
  fa[yy] = xx;
 } 
 else {
  fa[xx] = yy;
  if(r[xx] == r[yy]){
   r[yy] ++;
  }
 }
}
// a    表示同类
// a+n  表示 a 的猎物 
// a+2n 表示 a 的天敌 
int main (){
 cin>>n>>m;
 for(int i = 1; i<= 3*n;i++){
  fa[i] = i;
 }
 for(int i = 1; i <= m;i++){
  cin>>t>>x>>y;
  if( x > n || y > n ){ cnt++;continue; } //超出范围的不算
  else if(t == 1){//y 是 x 的同类 
   if(find(x+n) == find(y) || find(x+2*n) == find(y)){
    cnt++;continue;
   } 
   merge(x,y);
   merge(x+n,y+n);
   merge(x+2*n,y+2*n);//合并关系//这里用天敌猎物论可以很好相出来怎么写
  }
  else if(t == 2){//y 是 x 的猎物
   if(find(x) == find(y) || find(x+2*n) == find(y)){
    cnt++;continue;
   }
   merge(x+n,y);
   merge(x+2*n,y+n);
   merge(x,y+2*n);//合并关系
  }
 }
 cout<<cnt<<endl;
 return 0;
}

04 P1525 关押罪犯 ¶

P1525 关押罪犯

贪心的搞一下，排个序把爱搞事情的，打架_~nb~的两个大哥分开

 sort(per+1,per+m+1,cmp);

关系数量由2变到了1 罪犯只有两个去处，要么在这个监狱，要么在那个监狱 ~~（我的门前有两颗树，一颗是枣树，另一颗还是枣树）~~ ~~（逃 ~~~

 for(int i = 1; i <= m; i++){
  if( find(per[i].x) == find(per[i].y) ){
   fl = 1;
   cout<<per[i].w<<endl;break;
  }
  merge(per[i].x+n,per[i].y);
  merge(per[i].x,per[i].y+n);//合并罪犯
 }
 if(fl == 0){
  cout<<"0"<<endl;
 }

05 银河英雄传说 ¶

P1196 [NOI2002] 银河英雄传说 带权并查集 所谓带权，就是要维护一个权（在本题中是树的深度）的数组

//Author:PhilFan;
//银河英雄传说--并查集 
#include<bits/stdc++.h>
using namespace std;
#define maxn 40000 
int fa[maxn],d[maxn],size[maxn];
int t,x,y,xx,yy;
char c;

int find(int x){  //查询函数 
 if(fa[x] == x) return fa[x];
 int root = find(fa[x]);
 d[x] += d[fa[x]]; //维护数组 d，记录边权求和 //合并的时候加上另一个树的全部深度
 return fa[x] = root;//路径压缩 //
}
void merge(int x ,int y){//合并数组 
 x = find(x); y = find(y); //找祖宗 
 if(x != y){
  fa[x] = y;   //~~换爸爸？？~~//merge 
  d[x] += size[y]; //深度是加到的那颗树的战舰数量 
  size[y] += size[x];//战舰数量求和 
  size[x] = size[y]; 
 }
}
int main()
{
 for(int i = 1; i <= 30000; i++){//初始化 
  fa[i] = i;
  size[i] = 1;
 }
 cin>>t;
 for(int i = 1; i <= t; i++){
  cin>>c>>x>>y;
  xx = find(x),yy = find(y);
  if(c == 'M')  merge(xx,yy);      //合并 (并 
  else if(c =='C'){// 查 
   if(xx == yy) cout<<abs(d[y] - d[x])-1<<endl; //不包括端点，绝对值 -1； 
   else    cout<<"-1"<<endl;
  }
 }
 return 0;
}

P2342 叠积木 ~~双倍经验~~ 别怪我没告诉你