并查集 ¶
约 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 模板 - 并查集 ¶
//按秩合并
#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);
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;
}