[算法]并查集以及优化

这是Wikipedia中对并查集的介绍：

在计算机科学中，并查集（英文：Disjoint-set data structure，直译为不交集数据结构）是一种数据结构，用于处理一些不交集（Disjoint sets，一系列没有重复元素的集合）的合并及查询问题。并查集支持如下操作：

• 查询：查询某个元素属于哪个集合，通常是返回集合内的一个“代表元素”。这个操作是为了判断两个元素是否在同一个集合之中。
• 合并：将两个集合合并为一个。
• 添加：添加一个新集合，其中有一个新元素。添加操作不如查询和合并操作重要，常常被忽略。

由于支持查询和合并这两种操作，并查集在英文中也被称为联合-查找数据结构（Union-find data structure）或者合并-查找集合（Merge-find set）。

“并查集”可以用来指代任何支持上述操作的数据结构，但是一般来说，“并查集”特指其中最常见的一种实现：不交集森林（Disjoint-set forest）。经过优化的不交集森林有线性的空间复杂度（O(n)，n为元素数目，下同），以及接近常数的单次操作平均时间复杂度(O(log*(n)),log*(n)为反阿克曼函数）)是效率最高的常见数据结构之一。

并查集是用于计算最小生成树的克鲁斯克尔演算法中的关键。由于最小生成树在网络路由等场景下十分重要，并查集也得到了广泛的引用。此外，并查集在符号计算，寄存器分配等方面也有应用。

基本并查集

首先从最简单的开始，我们先完成并查集查询，合并和添加的操作。

表示

一般我们使用树的形式表达一个并查集集合。大概就像这样

这里有两个集合，以0为根节点的，以5为根节点的。

添加

添加操作MakeSet(x)添加一个元素x，这个元素单独属于一个仅有它自己的集合。在不交集森林中，添加操作仅需将元素标记为根节点。
首先，为了简单理解我这里使用一个数组表示出并查集的节点。

int djs[100];

我们要保留它的数据，还要保留它的根节点，所以在这里，我们简单定义成这样。MakeSet函数里对节点初始化，让root指向自己。

void MakeSet(int x) {
  djs[x] = x;
}

查询

在不交集森林中，每个集合的代表即是集合的根节点。查询操作Find(x)从x开始，根据节点到父节点的引用向根行进，直到找到根节点。
这段代码也很简单：

int Find(int x) {
    if(djs[x] == x)
        return x;
    return Find(djs[x]);
}

合并

合并操作Union(x, y)把元素x所在的集合与元素y所在的集合合并为一个。合并操作首先找出节点x与节点y对应的两个根节点，如果两个根节点其实是同一个，则说明元素x与元素y已经位于同一个集合中，否则，则使其中一个根节点成为另一个的父节点。

用图来说就是在将图1对以0为根节点与以3为根节点的集合合并后就会变成图2


代码这样写：

void Union(int x, int y) {
    djs[Find(y)] = djs[Find(x)];
}

好了现在你已经学会并查集了，做一下这道题吧Islands

优化

上边这些代码好吗？他不好，因为在最坏情况下会Union成一条链，这时候Find操作是O(n)的

{0,0,1,2,3,4,...}
对这种情况我们肯定是要优化他的，优化肯定是从Union入手了，常见的优化方法有两种，一种是根据权重，另一种是根据树的深度，这时候情况就有点复杂了，无论是权重还是深度，显然都不是一个数组就能解决的了的，所以我们可以再引入一个数组来保存。
下边以权重为例¹

int djs[100];
int power[100];
void MakeSet(int x) {
    djs[x] = x;
    power[x] = 1;
}

int Find(int x) {
    if(djs[x] == x)
        return x;
    return Find(djs[x]);
}

void Union(int x, int y) {
    int a = Find(y);
    int b = Find(x);
    if(power[a] < power[b])
        std::swap(a,b);
    djs[a] = djs[b];
    power[a] += power[b];
}

这样就可以通过权重选择合并的树了，这时候查找达到了O(log(n))的。
难道这就是极限？
还记得刚开始提到的反阿克曼函数吗？它的优化可以达到什么地步呢？
2^65535 的数据均摊也只需要五步就可以找到他的根节点！这就是通过路径压缩算法实现的。

路径压缩

对于这样的一颗树，我现在执行了查找7的根节点的操作

我们在Find(7)的时候都经过了哪些节点？
（7,6,5,0），如下：

这时候我让这条路径所有节点的根节点都之间变成根节点0，就成了这样

这时候，下次再查这条路径上的节点的根节点的时候，都只需一步就可查出结果。
代码实现我选择新建vector来保存，只要修改一下Find就好了。

std::vector<int> temp;
int Find(int x) {
    temp.push_back(x);
    if(djs[x] == x)
        return x;
    int root = Find(djs[x]);
    for(int v : temp) {
        djs[v] = root;
    }
    temp.clear();
    return root;
}