并查集——简单并查集

对于并查集的定义其实并不难理解

通俗的理解可以是：你是我的亲戚，他是我的亲戚，那你和他同样也是亲戚。通过合并而查索之的操作，可以实现在较小的时间复杂度下完成对一些不交集的 合并 及 查询 问题

通常会有两种操作：查询和合并

查询 find()

通俗地讲一个故事：几个家族进行宴会，但是家族普遍长寿，所以人数众多。由于长时间的分离以及年龄的增长，这些人逐渐忘掉了自己的亲人，只记得自己的爸爸是谁了，而最长者（称为「祖先」）的父亲已经去世，他只知道自己是祖先。

为了确定自己是哪个家族，他们想出了一个办法，只要问自己的爸爸是不是祖先，一层一层的向上问，直到问到祖先。如果要判断两人是否在同一家族，只要看两人的祖先是不是同一人就可以了。

在这样的思想下，并查集的查找算法诞生了。——OI-WIKI

一种简单的实现如下

int find(int x)
{
    // 寻找x的祖先
    if (fa[x] == x) // 如果x是祖先则返回
        return x;
    else
        return find(fa[x]); // 如果不是则x的爸爸问x的爷爷
}

合并 unity()

宴会上，一个家族的祖先突然对另一个家族说：我们两个家族交情这么好，不如合成一家好了。另一个家族也欣然接受了。

我们之前说过，并不在意祖先究竟是谁，所以只要其中一个祖先变成另一个祖先的儿子就可以了。

在这样的思想下，并查集的合并算法诞生了。——OI-WIKI

void unity(int x, int y)
{
    x = find(x);
    y = find(y);
    fa[y] = x; // 把 y 的祖先变成 x 的祖先的儿子
    return;
}