并查集——简单并查集

并查集——简单并查集

/ 0评 / 2588次 / 0

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

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

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

查询 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;
}
合并前
合并后

发表回复

您的电子邮箱地址不会被公开。

你好 No.65347