并查集是一种用互质的集合对数据进行分类管理的数据结构。
并查集主要实现了两个功能：合并与查询
我们用一个数组fa来表示第i个元素所在集合的根节点。
根节点的父节点指向它自身。
初始的时候，我们把fa=i，这样就初始化了n个互质的集合。
然后当要合并两个节点x、y所在的集合的时候，就先找到他们的根节点（代表元），然后将一个集合的根节点指向另一个节点的根节点即可。
判断两个元素所在集合是否相同，其实就是去找他们所在集合的代表元。代表元相同，那么就证明这两个元素在同一个集合里面。
对于题目DSL_1_A来说，题目要求实现一个简单的并查集，代码如下：
对于上面这个题目，我们会发现，运行的状况是这样的
这虽然是AC了，可是耗时有点高啊，耗时0.4s，n的数据范围是，操作数最大为0。这怎么看都不像一个时间复杂度低于O(logn)的算法啊。
那么肯定是有优化空间的。
路径压缩但是，这样子的话，每次查找都需要递归很多次，非常的费时。我们就可以在合并集合的时候，做路径压缩来解决这个问题。
路径压缩就是，把一个集合里面，正在合并的节点都的父节点都指向合并时的根节点。这样使得路径得到了压缩，减少了查询的耗时。
怎么说吧，我觉得路径压缩有点动态规划的思想在里面，就是每次查询找到当前节点的根节点之后，就更新进去fa数组，然后下次用到这个值的时候，就可以减少调用的次数了。
代码实现如下：
intfind_root(intx){if(fa[x]==x)returnx;intt=find_root(fa[x]);fa[x]=t;returnt;}按秩合并
并查集的按秩合并说白了就是把高度矮的树合并到高度高的树上。
按秩合并能显著降低最长路径长度，这样的话，在查询的时候可以更快地查询到根节点。只有使用了路径压缩+按秩合并的并查集，时间复杂度才会低于O(logn)
我们需要使用一个数组Rank来存储第i个节点作为根节点时，它的树的高度。
那么我们发现，需要更新Rank的情况只有是在合并集合且两个集合树高相等时，才需要把一个集合的根节点的树高+1。
具体的代码实现就是，初始化一个全局数组Rank，把它的值都设为0，接着，把合并集合的函数改成下面这样：
voidunite(intx,inty){intfx=find_root(x);intfy=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，来存储当前节点到路径压缩后的父节点的权值和。查询的时候，进行路径压缩，并更新s的值。
在合并的时候，需要对新的这条连边赋值，看下面这个图就知道了。
已知：C-A=z
那么根据初中数学知识就可以知道，D-B=y+z-x
接着，给新建立的连边赋值就好了。
龙进点滴赞赏，弥足珍贵