算法总结(1)-并查集与带权并查集

并查集是我在进入acm后学的第一个数据结构了，因为思路简单和代码短我倒是很快就记住了，但是深入理解可能就差了一些，比如真实复杂度之类的。
那第一篇总结就写写并查集好了

并查集

并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。常常在使用中以森林来表示。 -来自百度百科

引入

并查集一般用于解决元素的分组问题，很多时候可以用来合并多个元素到一个集合从而达到简化问题的作用。
并查集的思想就是，最初，每个元素都各自属于一个集合，即可以定义一个数组pre[i]代表i元素的祖先，因为最开始每个元素单独为一个集合，所以其祖先就是自己。
接下来若两个元素产生关系，需要将两个元素纳入同一个集合，那这时需要的就是将其中一个元素的祖先指向另一个元素，他们的最大（等级最高，也就是处于树根位置的祖先）祖先相同（祖先的祖先也是我的祖先），就可以认为他们处于同一个集合。
因此对于这个数据结构我们需要合并和查询两种操作，分别用来将两个集合合并为一个集合，和查询一个节点的最大祖先。

查询

查询操作就是查询到该元素的最大祖先，最大祖先有一个特征，就是他的祖先是指向自己的，因此，代码如下。

int Find(int x)
{
    return x == pre[x] ? x : Find(pre[x]);
}

代码非常简单，使用递归查找祖先指向自己的元素即可，该元素就为这个集合的最大祖先。

合并

合并操作，就是指将两集合合并到一起，最简单的方法，就是让两个集合的最大祖先产生联系，这样他们两个集合的最大祖先相同，即代表所有元素处于同一个集合。

void union(int x,int y)
{
    pre[Find(x)] = Find(y);
}
同样一行代码解决，直接将x的最大祖先的祖先指针指向y的最大祖先即可。这样x与y的最大祖先相同也就代表他们在同一个集合内了。

路径压缩

当我们需要合并的元素过多时，在最坏情况下，并查集的树形结构会退化为一条链，这样Find操作的复杂度就会退化到O(n)。
那如何尽量避免这种情况呢，就是下面提到的路径压缩。
当我们在查询一个元素的祖先节点时，可以在递归返回最大祖先时，顺便将路径上经过的元素的祖先指针全部指向最大祖先。同样在Find查询操作时就可以顺遍完成。
路径压缩查询代码

int Find(int x)
{
    return x == pre[x] ? x : Find(pre[x]);
}

按秩合并

按秩合并是指将退化的并查集中每个集合尽量优化为树状结构。也许有人认为不是已经路径压缩了，就不需要再次优化树结构了。大多数情况下是如此的。但是在极端情况下，即每次新增节点均与该集合的祖先节点相连，即运行合并操作union(x,y)时，xy均为祖先节点，这时union操作中的Find操作并没有进行递归查询，也就没有进行路径压缩。这时，并查集中的树的深度仍然很高，也就是操作仍然需要消耗大量时间。因此按秩合并在极端情况下仍是有必要的.

inline void merge(int i, int j)
{
    int x = Find(i), y = Find(j);
    if (rank[x] <= rank[y])
        pre[x] = y;
    else
        pre[y] = x;
    if (rank[x] == rank[y] && x != y)
        rank[y]++;
}

代码中rank即为秩，也就是节点在树中的深度。最初应初始化为1.

带权并查集

带权并查集的含义就是，将元素与其父亲节点的关系存储下来。
而在大多的题目中，关系一般是存在循环的，比如经典例题POJ1182
食物链中三种关系是循环的，设0为捕食1为同级2为被捕食的时候，我们可以发现，若a与b的关系为捕食，b与c的关系为同级，那么a与c的关系也是为捕食，则
那么查找操作可以改为

int Find(int x){ 
    if(x == pre[x]) return x;
    else{   
        int temp = pre[x];
        pre[x] = Find(pre[x]); 
        rela[x] = (rela[x] + rela[temp]) % 3; // 压缩路径关系
    }
    return pre[x];
}

同样，合并操作也可以改为

void union(int x, int y, int r){
    int p = Find(x);
    int q = Find(y);

    if(p != q){
        pre[p] = q; 
        rela[p] = (rel[y] - rel[x] + r + 3) % 3;
    }
}

和普通并查集的区别仅仅在于需要多考虑一下关系的更新即可。