什么是并查集？
并查集是一种树型的数据结构，常用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。
并查集可以高效的进行如下操作：
- 合并两个不相同的集合
- 判断两个元素是否属于同一个集合
并查集常见操作
init()初始化所有元素独立为一个集合(即父节点是自身)
- 定义数组fa[],fa[x]存储x的父节点。
- 初始化所有元素的父节点为-1,若fa[x]=-1则代表元素x自身为一个集合。
void init(){
memset(fa,-1,sizeof(fa));//
}
find()查找元素所在的集合返回根节点
- 如果x独立为一个集合，返回x，否则返回fa[x]。
int find(int x){
if(fa[x]==-1) return x;
return find(fa[x]);
}
unite(x,y)合并两个不相同的集合
- 先找到x和y的代表元素。
- 如果相同，则说明x和y已经属于同一个集合，不用处理。
- 如果不同，将一个代表元素指向另一个代表元素。
void unite(int x,int y){
x=find(x);
y=find(y);
if(x==y) return;
fa[x]=y;
}
same(x,y)判断两个元素是否属于同一个集合
- 分别找到x和y的代表元素。
- 如果相同，说明x和y属于同一个集合。
bool same(int x,int y){
return find(x)==find(y);
}
并查集的优化
路径压缩
寻找父节点是采用递归的方法，不采取任何判断的合并，树有可能会退化成一条链，每次find都会是O(n)的复杂度。所以必须进行路径压缩。在我们找到根节点的时候，直接把根节点作为它的父节点。
int find(int x){
if(fa[x]==-1) return x;
return fa[x=]find(fa[x]);
}
按树的高度合并
合并时将元素所在深度低的集合合并到元素所在深度高的集合。
- 定义一个deep[]数组，默认只有一个节点的集合深度为0；
- 在unite()操作中，判断x和y的高度，将高度小的树连接到另一颗树的根节点上。
void unite(int x,int y){
x=find(x);
y=find(y);
if(x==y) return;
if(deep[x]<deep[y]) fa[x]=y;
else{
fa[y]=x;
if(deep[x]==deep[y]) deep[x]++;
}
}
优化后的代码
int fa[N],deep[N];
void init(){
memset(fa,-1,sizeof(fa));
memset(deep,0,sizeof(deep));
}
int find(int x){
if(fa[x]==-1) return x;
return fa[x=]find(fa[x]);
}
void unite(int x,int y){
x=find(x);
y=find(y);
if(x==y) return;
if(deep[x]<deep[y]) fa[x]=y;
else{
fa[y]=x;
if(deep[x]==deep[y]) deep[x]++;
}
}
bool same(int x,int y){
return find(x)==find(y);
}
