带权的必要性
并查集的性能劣化最主要的是来源于子树过于庞大合并和判断需要时间过长，那么就需要通过带权来使得并查集在合并的时候变得更棒一点。使得子树深度变短而广度增加。
非带权并查集.png
int FindRoot(int i)
{
while (i != id[i]) i = id[i];
return i;
}
void union(int p, int q)
{
int i = FindRoot(p);
int j = FindRoot(q);
id[i] = j;
}
这段就是比较普遍的并查集入门的时候所写的合并和查找代码，问题出在哪里呢？如果一棵树过于瘦长的话，每一次回溯根节点都可能会是一个噩梦，因为树形结构如果没有合格的筛选的话可能会变成一条非常耿直的线段，这样子每一次合并之后回溯都会可能产生n的复杂度，如果进行m次合并操作，那么就可能会出现m*n的时间消耗。
带权并查集的代码
虽然说加入带权之后会带来非常大的性能提升，实际上它的代码量非常的短。首先，我们需要一个新的数组size来标记一开始的所有的节点的大小，因为其实一开始所有的节点都可以算作一棵独立的树，那么size的空间大小开和节点数一样就够了。然后在合并操作里面这样进行
void union(int p, int q)
{
int i = FindRoot(p);
int j = FindRoot(q);
if (i == j) return;
else if (size[i] > size[j]) {size[i] += size[j];id[j] = i;}
else {size[j] += size[i];id[i] = j;}
}
即可，因为这样子的话，其实每一次回溯的最坏情况也只会有lgN的时间消耗。
带权并查集时间复杂度的证明
在带权并查集里面，两棵树合并如果需要深度增长，当且仅当第二棵树的深度大于等于第一棵树，这样子的话就会需要到将第一棵树并入第二棵树中，其实相当于是将N棵树二分掉了一样，能够一直保持这相等或大于在N个大小的数里面最大只可能是lgN棵，所以在合并之后至多只可能便利lgN次，因此整个并查集的搭建只会需要N+M*lgN的时间复杂度，最后的结果图应该如此。
带权并查集结果图.png
并查集的展开
既然我们可以通过进行附加权的方式使得他们在合并的时候呈现一个接近好的树形结构，那么如果我们在将这样子的一棵并查集树展开会是怎么样的？只能说，那真的非常非常棒。在之前的回溯里面我们已经只需要进行lgn次操作就可以查找到了祖父节点，那么如果我直接在回溯的时候不断将它指向祖父节点呢？就会变成lglgn也就是lg*n这样一种复杂度，在进行2的65535次方次操作的时候，也就是lgx2的65535次方，仅仅需要五次就能够解决，这是一个接近于1的常数量级！
并查集的展开.png
这样的状态压缩的代码
非常非常非常简单，我知道之前带权并查集的代码仅仅两行已经非常简单了，但是这样一个会更加简单！
void FindRoot(int i)
{
while (i != id[i]) i = id[i];
return i;
}
void ExFindRoot(int i)
{
while(i != id[i])
{
id[i] = id[id[i]];//只有这一行。
i = id[i];
}
return i;
}
路径压缩的证明
其实我觉得聪明的读者们已经能够猜出为什么会变成一个lg*n的复杂度了。
很简单，因为在查询它的祖父的时候，用它的父亲又查询了一次，这样子又再一次调用了在带权之后已经转成了多叉树形式数据结构的并查集，因此在每一次操#作进行的时候实际上就会产生lg*的这样子的结果。
2016-12-27结语
实话说之前没有想过这方面的优化，总认为能用就可以了，优化是一种非常麻烦的事情，没有那么好的大脑是无法进行的。直到看到这玩意。。。。如果说正确的算法是将不可能的问题化成可能，将可能的问题尽量优化的话。那么“优雅”的算法更像是能将问题解决的同时调用最少的资源和最简短的语句。。我是真服了这个优化了。。
网友评论