并查集是一种用互质的集合对数据进行分类管理的数据结构。
并查集主要实现了两个功能：合并与查询
我们用一个数组fa[i]来表示第i个元素所在集合的根节点。
根节点的父节点指向它自身。
初始的时候，我们把fa[i]=i，这样就初始化了n个互质的集合。
然后当要合并两个节点x、y所在的集合的时候，就先找到他们的根节点（代表元），然后将一个集合的根节点指向另一个节点的根节点即可。
判断两个元素所在集合是否相同，其实就是去找他们所在集合的代表元。代表元相同，那么就证明这两个元素在同一个集合里面。
对于题目 DSL_1_A 来说，题目要求实现一个简单的并查集，代码如下：
代码语言：javascript复制#include<iostream>
#include<string.h>
using namespace std;
#define MAXN 10005
int fa[MAXN];
int n;
int find_root(int x)
{
if(fa[x]==x)
return x;
return find_root(fa[x]);
}
void unite(int x,int y)
{
fa[find_root(x)] = find_root(y);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=0;i<n; i)
{
fa[i] = i;
}
int q;
cin>>q;
int com,x,y;
for(int i=0;i<q; i)
{
cin>>com>>x>>y;
if(com==0)
{
unite(x,y);
}
else
{
cout<<(find_root(x)==find_root(y)?1:0)<<endl;
}
}
}对于上面这个题目，我们会发现，运行的状况是这样的
这虽然是AC了，可是耗时有点高啊，耗时0.4s，n的数据范围是10000，操作数最大为100000。这怎么看都不像一个时间复杂度低于O(logn)的算法啊。
那么肯定是有优化空间的。
路径压缩
但是，这样子的话，每次查找都需要递归很多次，非常的费时。我们就可以在合并集合的时候，做路径压缩来解决这个问题。
路径压缩就是，把一个集合里面，正在合并的节点都的父节点都指向合并时的根节点。这样使得路径得到了压缩，减少了查询的耗时。
怎么说吧，我觉得路径压缩有点动态规划的思想在里面，就是每次查询找到当前节点的根节点之后，就更新进去fa数组，然后下次用到这个值的时候，就可以减少调用的次数了。
代码实现如下：
代码语言：javascript复制int find_root(int x)
{
if(fa[x]==x)
return x;
int t = find_root(fa[x]);
fa[x] = t;
return t;
}按秩合并
并查集的按秩合并说白了就是把高度矮的树合并到高度高的树上。
按秩合并能显著降低最长路径长度，这样的话，在查询的时候可以更快地查询到根节点。只有使用了路径压缩 按秩合并的并查集，时间复杂度才会低于O(logn)
我们需要使用一个数组Rank[i]来存储第i个节点作为根节点时，它的树的高度。
那么我们发现，需要更新Rank[i]的情况只有是在合并集合且两个集合树高相等时，才需要把一个集合的根节点的树高 1。
具体的代码实现就是，初始化一个全局数组Rank[i]，把它的值都设为0，接着，把合并集合的函数改成下面这样：
代码语言：javascript复制void unite(int x,int y)
{
int fx = find_root(x);
int fy = find_root(y);
if(Rank[fx]>Rank[fy])
{
fa[fy] = fx;
}
else
{
fa[fx] = fy;
if(Rank[fx]==Rank[fy])
Rank[fy] ;
}
}再把代码提交上去，可以发现，运行时间减少到了0.05s，这差不多加速了10倍啊！
带权并查集
带权并查集就是在并查集的树的连边上附上权值。
带权并查集的合并，需要把权值也加起来。
其实理解并不困难，就是用一个数组s[i]，来存储当前节点到路径压缩后的父节点的权值和。查询的时候，进行路径压缩，并更新s[i]的值。
在合并的时候，需要对新的这条连边赋值，看下面这个图就知道了。
已知：C-A=z
那么根据初中数学知识就可以知道，D-B = y z-x
给新建立的连边赋值就好了。
转载请注明出处：https://www.longjin666.top/?p=749
