资讯

历史

科技

环境与自然

成长

游戏

财经

文学与艺术

美食

健康

家居

文化

情感

汽车

三农

军事

旅行

运动

教育

生活

星座命理

并查集之扩展域和边带权——以“食物链”为例

创作时间:

作者:

@小白创作中心

并查集之扩展域和边带权——以“食物链”为例

引用

CSDN

https://blog.csdn.net/WillHou/article/details/141758917

并查集（Disjoint-Set）是一种用于动态维护多个不相交集合的数据结构，支持快速的查询和合并操作。本文通过"食物链"这道经典题目，深入讲解了并查集的两个重要扩展：扩展域和边带权，帮助读者更好地理解和掌握这一算法。

并查集算法简单回顾

在这篇文章中，我们不会重复介绍并查集的具体实现原理，而是重点回顾其算法、优化和扩展。并查集的基本思想是"代表元"，即在每个集合中选择一个元素作为代表，其他元素只需标记与代表元的关系。这种思想类似于前缀和算法中只记录每个元素到起始位置的数值总和，但不同的是，并查集需要多个代表元来维护多个集合。

并查集的两个常见优化方式是路径压缩和按秩合并。路径压缩通过将每个非代表元元素直接指向代表元来优化find函数的时间复杂度。按秩合并则通过将节点较少的集合合并到节点较多的集合中来进一步优化时间复杂度。通过这两个优化，find函数的均摊复杂度可以达到O(α(n))，其中α表示反阿克曼函数，这个函数增长极其缓慢，几乎可以看作是常数时间复杂度。

扩展域

问题描述

在"食物链"这道题目中，动物王国中有三类动物A、B、C，这三类动物的食物链构成了有趣的环形：A吃B，B吃C，C吃A。每个动物都是A、B、C中的一种。题目要求判断一系列关于动物关系的陈述中，有多少条是假话。

样例分析

让我们通过一个样例来理解题目：

显而易见，下面几句话是假话：

第1句话，101 > 100，必为假话；
第4句话，表示自残，必为假话；

还有一句假话需要仔细理解题意。题目中提到："动物王国中有三类动物A、B、C，这三类动物的食物链构成了有趣的环形。A吃B，B吃C，C吃A。……每个动物都是A、B、C中的一种。"这句话告诉我们，两种动物之间只存在"捕食"和"同类"的关系，且"捕食"是单向的，不会存在A吃B同时B也能吃A的情况。

其次，由于只存在三种动物，并且其捕食关系构成环，因此一定有A的猎物的猎物是A的天敌，而不可能是A的同类或者猎物。

因此，我们可以发现，由于2是1的猎物（第2句话），3是2的猎物（第3句话），因此3是1的猎物的猎物，也就是1的天敌。但是第5句话说1和3是同类，也必为假话。

综上，对于该样例，答案为3。

解决方案

对于"同类"关系很好处理，因为"同类"关系总是满足传递性，也即A的同类的同类必为A的同类。这正是并查集最擅长维护的。

但对于"捕食"关系，并不好维护。因为"捕食"不具备传递性。相反，A的猎物的猎物竟然是A的天敌，这个关系并查集没法维护，它只能维护无向关系。

并查集维护有向关系，一个常见的技巧就是——"扩展域"。对于这个题，如下所示，可以如下维护：

维护一个并查集，由三个域组成：同类域，猎物域，天敌域。

若A与B是同类，则一定有：

A的同类与B的同类同类。
A的猎物与B的猎物同类。
A的天敌与B的天敌同类。

若A捕猎B，则一定有：

A的同类是B的天敌。
A的猎物是B的同类。
A的天敌是B的猎物。（在"只有三种动物"的情况下成立）

以上即可。

for (int i = 1; i <= m; i++) {
    int op, a, b;
    scanf("%d%d%d", &op, &a, &b);
    if ((a > n) or (b > n)) {
        ans++;
        continue;
    }
    if (op == 1) {
        if (judge(b, a+N) or judge(a, b+N)) {
            ans++;
            continue;
        }
        merge(a + N*0, b + N*0);
        merge(a + N*1, b + N*1);
        merge(a + N*2, b + N*2);
    } else {
        if (judge(a, b) or judge(a, b+N)) {
            ans++;
            continue;
        }
        merge(a + N*0, b + N*2);
        merge(a + N*1, b + N*0);
        merge(a + N*2, b + N*1);
    }
}

边带权

边带权给并查集的父子节点边加上了权值，这个权值可以用来描述父子关系。因为权值相较于扩展域开空间来表示关系的方式更加灵活，所以边带权比扩展域而言可以描述更加复杂的关系，应用范围因而更广。

但相较于扩展域而言，边带权无论从代码难度上还是思维难度上都要更高。因此，能用扩展域尽量用扩展域。

以这道题为例。每两个动物之间只会存在三种有向关系：同类、捕食、被捕食。我们可以用权值来表达这三种关系。

假设A为并查集某棵树上的代表元。如果A和B存在一条权值为0的边，那么表示A和B是同类；如果权值为1，那么表示B是A的猎物；如果权值为2，那么表示B是A的天敌。

由此，我们可以在读取每一句话后，通过权值检验某两个动物的关系。

那么如果要检验的两个动物没有一个是代表元怎么办？没有关系。因为三个动物间存在捕食环，所以可以把权值想象成绕着环沿着捕食方向走多少格。因此我们只需要求它们关于代表元的关系，即可获得它们之间的关系。例如B跟代表元A间权值为1（即B是A的猎物），而C跟A间权值为2（即C是A的天敌），那么一定可以推出B是C的天敌，这可以通过AB - AC = 1 - 2 = -1 ≡ 2 ( mod 3 )得到。我们将每个节点与其代表元之间的权值记为dis，即距离。

这一点表明了边带权的可行性。下面我们讨论怎么在并查集中维护这个权值。

我们发现，并查集中有两个地方会涉及到权值的更改：find函数路径压缩时和merge函数转移代表元时。我们分别讨论这两个情况如何维护。

维护`find`函数

路径压缩时，我们需要把父节点的权值叠加到子节点。根据上面的环，这并不会影响到动物的关系。

但这也提醒我们，在路径压缩后，边的权值不再是[0,2]间的数。但这个问题很好解决，只需对权值模3取余即可。

维护`merge`函数

如下图，若B和D分属两树，且现知B和D同类，应该如何merge？

显然，我们需要在两棵树的代表元A和C间建立一条带权值的边。这条边的权值需要保证B和D之间的关系能够被保证。设这条边的权值为w，则有：

disB + 0 ≡ disD + w ( mod 3)

其中+0的意思是两动物同类。类似的，如果是猎物关系则+1，天敌关系+2。于是解得：

w ≡ disB + 0 - disD ( mod 3)

调用`judge`函数

在边带权中，judge函数不仅承担了判断两节点是否属于同一集合的作用，还被用来判断两节点间的关系。

具体的，在这道题中，只要两节点同属一个集合中，我们只需要将两节点dis值相减，看看差模3的余数即可。

但差有可能为负数。所以我们这里采取一个小技巧：判断a和b除以m的余数是否等于k，只需要(a - b - k) % m == 0即可。这个由同余基本性质可以证明。

通过这个小技巧，我们也无需担心上面的w的正负问题了。因为在C++中，(-3) % 3的结果也是0。所以上面w的计算式就被简化为：

w = disB + 0 - disD ( mod 3)

代码示例

以上便是分析的过程。下面是关键代码，为了方便理解，我将merge函数和judge函数写在main函数里了，但find函数因为要递归，就只能写在外面了。

int find(int a) {
    if (djs[a] != a) {
        int t = find(djs[a]);
        dis[a] += dis[djs[a]];
        djs[a] = t;
    }
    return djs[a];
}
for (int i = 1; i <= n; i++)
    djs[i] = i;
for (int i = 1; i <= m; i++) {
    int op, a, b;
    scanf("%d%d%d", &op, &a, &b);
    if ((a > n) or (b > n)) {
        ans++;
        continue;
    }
    int ra = find(a), rb = find(b);
    if (op == 1) {
        if (ra == rb and (dis[a] - dis[b]) % 3) {
            ans++;
        } else if (ra != rb) {
            djs[ra] = rb;
            dis[ra] = dis[b] - dis[a];
        }
    } else {
        if (ra == rb and (dis[a] - dis[b] - 1) % 3) {
            ans++;
        } else if (ra != rb) {
            djs[ra] = rb;
            dis[ra] = dis[b] - dis[a] + 1;
        }
    }
}

这个代码没有用启发式合并，因为实现较为复杂。