并查集原理

并查集

将一些元素分组，形成不同的集合，然后可以对这些集合进行很快的合并和查询的数据结构就是并查集。
当操作次数特别多时，朴素的合并集合的方法会耗费大量的时间，这时候使用并查集是一个不错的选择。
并查集中，使用一个集合中的某个元素来标记这个集合，这和元素任意。我们把这个用来标记整个集合的元素称为最大老大。定义数组fa(father..)，fa[x]所在的集合就是x所在的集合，fa[x]是x的直系老大。当fa[x]==x时，这个x就是最大老大了。
有了上面的关系，可以知道一个集合里的元素最终指向的老大肯定是这个集合的最大老大。而合并两个集合的时候，在这两个集合的两个最大老大里任选一个作为合并后的最大老大即可。
这就是并查集的基本原理。
那么初始时，每个元素自成一个集合。

for (int i=1;i<=n;i++)
    fa[i] = i;

操作1：查询两个元素是否在一个集合中
只需检查这两个元素的最大老大是否相等即可！

查找一个元素的最大老大

int find(int x){
    if (x==f[x])    return x;
    return fa[x] = find(fa[x]);
}

在上述代码中，若x==fa[x]，x就是最大老大，这是递归终止条件。
否则，返回find(fa[x])。同时，我们知道，一个集合中的直系老大越少，即越多的元素直接指向最大老大，每次查找的速度就越快，所以有fa[x] = find(fa[x]);
还可以在进一步的优化，不使用递归来完成这个工作。

int find(int x){
    while (x!=fa[x])    x = fa[x] = fa[fa[x]];
    return x;
}

相比使用递归，其实快不了多少，，，，只是把递归变成了迭代而已。
和递归不同的是，若fa[x]不是x的最大老大，fa[x]最终的赋值也不一定是最大老大(在递归中是的！)。

合并两个集合

把两个元素的最大老大合并即可。

fa[find(x)] = find(y);

x，y的次序并不重要！