带权并查集

　　学习带权并查集之前我们需要先对并查集和路径压缩压缩了解，有需求的可以参考这篇博客。

刚昨天总结了并查集的相关操作，今天做题的时候居然发现自己一直都是存在一些想不到的地方，总是会存在一些漏洞，最骚的是今天做到了食物链这道题......才知道了带权并查集和种类并查集......好了接下

来就要进入带权并查集了。

　　上面的博客中有写到路径压缩的相关操作，我们知道路径压缩的结果就是同一集合中的所有元素统一指向树根，这样可以加快访问速度。和路径压缩一样，带权并查集仅仅是在每个集合元素都指向树根

的前提下赋予这些结点相对于树根的权值。

　　那么我们就需要用一个数组一个元素相对于他所属集合树根的权值，我们用value存储。

　　我们已经知道了基本并查集的一般实现，但是如果加入了value要如何实现呢。

　　我们思考：

　　　　在find函数中，我们对于每个元素进行一次赋值，使得最终所有元素的父亲结点都指向树根结点，那么如果带有权值的话，我们知道每次都会改变一个结点的父亲，知道找到他所属集合的树根，所以

　　我们每次也需要更新对应的value值。

　　　　那么合并函数呢，我们知道每次合并我们会将x所属集合的树根px的父亲设置为y所属集合的树根py，这样就可以将两个集合合并，那么我们知道在这过程中我们改变了px的父亲，也就需要改变px对

应他父亲的权值，我们根据下图就可以知道，对于value[px]，因为x最终父亲为py，所以显然两条路的权值应该相等，我们就可以得出如下代码。

　　　　并不是所有类型的更新都是下面这种情况，具体情况具体分析，但是思路宝贵。

 1 #include <cstdio>
 2 #include <cstring>
 3 using namespace std;
 4 
 5 const int maxn = 10000 + 5;
 6 int head[maxn], value[maxn], rank[maxn];
 7 
 8 int find(int u) {
 9     if(u != head[u]) {
10         int t = head[u];
11         head[u] = find(head[u]);
12         value[u] += value[t];
13     }
14     return head[u];
15 }
16 
17 void Union_Set(int x, int y, int s) {
18     int fx = find(x), fy = find(y);
19     if(fx == fy) return;
20     if(rank[fx] > rank[fy]) {
21         head[fy] = fx;
22         value[fy] = -value[y] + value[x] + s;
23     } else {
24         head[fx] = fy;
25         value[fx] = -value[x] + value[y] + s;
26         if(rank[fx] == rank[fy]) rank[fy] ++;
27     }
28 }
29 
30 int is_same(int x, int y) {
31     return find(x) == find(y);
32 }
33 
34 int main () {
35 
36     return 0;
37 }

　　后续会更新相关题目：针对题目再做详细描述。

带权并查集

推荐阅读