并查集详解
文章目录
- 1.概论
- 2.具体实现
- 2.1 路径压缩
- 2.2 按秩合并（启发式合并）
- 3.例题
1.概论
定义：
并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题（即所谓的并、查）。比如说，我们可以用并查集来判断一个森林中有几棵树、某个节点是否属于某棵树等。
主要构成：
并查集主要由一个数组fa，两个函数find( )、join( )构成。
fa数组用来存储每个点的前驱节点是谁，函数 find(x) 用于查找指定节点 x 属于哪个集合，函数 join(x,y) 用于合并两个节点 x 和 y 。
作用：
并查集的主要作用是求连通分支数（如果一个图中所有点都存在可达关系（直接或间接相连），则此图的连通分支数为1；如果此图有两大子图各自全部可达，则此图的连通分支数为2……）
2.具体实现
2.1 路径压缩
普通的查找比较耗费时间，可以把查找进行路径压缩优化，与普通的相比就多了一个赋值语句，但我们发现这个树被“压扁了”。如果我们再进行访问刚才的节点只需两步就可以了。所以find函数会把从x到根的路径压缩，使路径上的点指向根，大大降低查询时间。
int find(int x){if(fa[x]==x)return x;return fa[x]=find(fa[x]);
}
2.2 按秩合并（启发式合并）
下面是正常的合并，直接让其中一个集合的根（叫做代表元），使它的父节点为另一个集合的根，但还可以进行优化
void join(int x,int y){fa[find(x)]=find(y);
}
如果我们把大的集合并在小的集合下面，就会发现有更多的元素被降一级，所以我们按照集合的大小进行合并；把小的集合合并在大的下面，这样查找会更加的高效。
vector<int> siz(N,1); //记录并初始化子树的大小为 1，因为并查集初始化时每个点都是独立的点
void join(int x,int y){x=find(x),y=find(y); //查找两集合的根if(x==y) return ; //如果根相同就在同一个集合，没有必要进行合并if(siz[x]>siz[y]) //如果根为x的集合大于根为y的集合，就进行交换两个根的值swap(x,y); //这样x存的就是集合元素少的根的值fa[x]=y; //让集合小的根x的父节点为ysiz[y]+=siz[x]; //y集合数量增加
}
bool join(int x,int y)
{x = find(x); //寻找 x的代表元y = find(y); //寻找 y的代表元if(x == y) return false; //如果 x和 y的代表元一致，说明他们共属同一集合，则不需要合并，返回 false，表示合并失败；否则，执行下面的逻辑if(rank[x] > rank[y]) pre[y]=x; //如果 x的高度大于 y，则令 y的上级为 xelse //否则{if(rank[x]==rank[y]) rank[y]++; //如果 x的高度和 y的高度相同，则令 y的高度加1pre[x]=y; //让 x的上级为 y}return true; //返回 true，表示合并成功
}
例如，上面图片中的x=6和y=9元素；6的根为1，9的根为7；更新x=1，y=7；根为1的集合大小为6，根为7的集合大小为3；siz[x]>siz[y]，所以交换x，y的大小；x=7，y=1。让根7的父节点等于1，fa[x]=y，就完成了合并。
3.例题
例题链接
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int m,n;
vector<int> siz(N,1);
int fa[N]，rank[N];
int find(int x){ //递归查找if(fa[x]==x)return x;return fa[x]=find(fa[x]);
}
void join(int x,int y){fa[find(x)]=find(y); //让其中一个集合的根，使它的父节点为另一个集合的根
}
int main(){cin>>n>>m;int x,y,z;for(int i=1;i<=n;i++){fa[i]=i; //每个点的父节点是它自己rank[i]=1; //每个节点构成的高度为1}while(m--){cin>>z>>x>>y; // z代表种类 if(z==1) //等于1代表合并 join(x,y);else{ //2代表查询是否在同一集合内 x=find(x),y=find(y);if(x==y) cout<<"Y"<<endl;else cout<<"N"<<endl;}}
}