维护例如“亲戚的亲戚是亲戚”这种关系的数据结构:并查集

维护例如“敌人的敌人是朋友”这种关系的数据结构:种类并查集

并查集

分析

并查集通常使用数组来实现,例如我们有 0、1、2、3、4 五个元素,用 int father[5] 来存储,该数组的下标为数组元素,值为父节点(下文会解释)。

初始化时,令 father[i] = i,即 father[0] = 0, father[1] = 1, father[2] = 2, father[3] = 3, father[4] = 4.

此时代表着,这五个元素自成一派,一共有五类元素。用以下图来表示:

如果我们要将 0、1 分为一类,2、3、4 分为另一类,那么我们需要这样设置:father[1] = 0, father[3] = 2, father[4] = 2,此时我们称 1 的父节点是 0,3、4 的父节点是 2。此时 0 和 2 为根节点,我们将父节点为自身的节点叫根节点,从下图可以形象地理解。

如果我们要把这两类合成一类呢,可以直接设置:father[2] = 0,即将一类的根节点指向另一类的根节点

上面,已经讲了并查集的初始化和合并操作,并查集还剩下一种操作,就是查询。我们可以查询两个元素的根节点是否相同,如果相同那么我们就能判断这两个元素属于一类,反正不属于一类。

查询操作使用递归,我们查询该节点的父节点,再查询父节点的父节点直到根节点。以上图 9 为例:

  • father[4] != 4 可知 4 不是根节点
  • father[4] == 2 可知 4 的父节点是 2
  • father[2] != 2 可知 2 不是根节点
  • father[2] == 0 可知 2 的父节点是 0
  • father[0] == 0 可知 0 就是根节点,查询完成,得到 4 的根节点为 0.

代码实现

初始化:

int fa[MAXN];
inline void init(int n)
{
    for (int i = 1; i <= n; i++)
        fa[i] = i;
}

查询:

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

合并:

inline void merge(int i, int j)
{
    fa[find(i)] = find(j);
}

优化

路径压缩

在并查集中,合并元素常常会使树的深度越来越大,而我们的查询操作是采用递归,层层向上查询。如果元素的深度太大,那么我们的查询效率会很低,因此我们需要优化元素的排布。

因为进行该优化得查询根节点,我们不妨就将它与查询操作合并到一起,这样我们每次查询就顺带优化了该并查集。如下图:

查询(路径压缩)

// 展开版本
int find(int x)
{
    if(x == fa[x])
    {
        return x;
    }
    else
    {
        fa[x] = find(fa[x]); // 多了这一个操作,将该节点的父节点直接设置为根节点
        return fa[x];
    }
}
// 单行版本
int find(int x)
{
    return x == fa[x] ? x : (fa[x] = find(fa[x])); // 注意此处的括号,?的优先级比=高
}

按秩合并

理想状况下,经过路径压缩操作,整个并查集应该为一个深度为 2 的树。但是路径压缩操作只在查询操作时进行,并且也只会压缩单条路线,不会优化整个并查集。

如上图,如果我们要合并这两个树,如果将 6 合并到 1,会得到下图左边的结果,深度为 3,如果将 1 合并到 6,会得到下图右边的结果,深度为 4。由此可见,如何合并两个树,对结果的深度有影响。

为了查询效率我们当然要让树的深度越小越好,简单分析可以得到,应当将深度小的树合并到深度大的树,这样深度不变。如果两树深度相同,那么如何合并结果是一样的,深度都会增大 1。我们要比对树的深度,因此需要额外的数组 rnk[ ] 来保存该节点的子树的深度。

初始化(按秩合并)

int fa[MAXN], rnk[MAXN];
inline void init(int n)
{
    for (int i = 1; i <= n; i++)
    {
        fa[i] = i;
        rnk[i] = 1;
    }
}

合并(按秩合并)

void merge(int i, int j)
{
    int x = find(i), y = find(j);
    if (rnk[x] <= rnk[y])
        fa[x] = y;
    else
        fa[y] = x;
    if (rnk[x] == rnk[y] && x != y)
        rnk[y]++;
}

第一个 if 控制合并方式,将深度小的树合并到深度大的树。

第二个 if 维护 rnk[ ] 数组,当深度相同两树合并时,深度才会 +1。

例题

POJ2524 - Ubiquitous Religions: http://poj.org/problem?id=2524

种类并查集

有时候,我们并不知道哪些元素应该为一类,只知道哪些元素不能为一类,此时一般并查集就没法处理这种问题了。

例题

POJ2492 - A Bug's Life: http://poj.org/problem?id=2492

POJ1182 - 食物链: http://poj.org/problem?id=1182

分析

借助第一个例题来具体分析:已知虫子有两种性别,我们简称为 A、B。输入告诉我们有几只虫子,也告诉我们这几只虫子之间的配对关系,也就是性别不同进行配对,然后我们需要判断这种配对关系是否出现矛盾(即出现了同性配对的情况)。

我们可以发现,如果我们想用一般并查集把虫子分成 A、B 两类,就会发现每组配对关系,到底谁是 A 谁是 B 是不确定的,那这就没法解决了。

这时就要用到种类并查集,种类并查集的所有代码都和一般并查集一样,不同的是使用方法。

初始化

本题有两种性别,那么就要初始化两倍大小的并查集。$1\sim N$ 和 $N+1\sim 2N$ 就可以表示出两种性别。(第二个例题有三个种类,那就得开三倍大小)

合并

例如我们要表示 1、2 虫配对,即 1、2 虫不能为同性,我们就要将 1 和 6、2 和 5 合并。推广来说,如果要配对 $A$、$B$,那么就要合并 $A$ 和 $B+N$、$B$ 和 $A+N$。

如果再表示 2、4 虫配对,那么就再将 2 和 8、4 和 6 合并。

于是 1、4 虫就通过 6 间接连接到了一起,2 通过 5 与 8 建立关系,最后 1、4、(6) 为一组,2、(5)、(8) 为一组。

那我们如何判断是否有矛盾呢?只需要判断两虫是否在同一组即可,因为同一组的含义为。例如我们将 1、4 配对,发现 1、4 在同一组(即 find(1) == find(4)),那么就表明出现矛盾。于是本题只需每次添加新关系时,判断 find(a) == find(b) 就能得知是否有矛盾了。

标签: 并查集, 种类并查集

添加新评论