并查集的高级用法——权值并查集与种类并查集

并查集

并查集，或称DSUDisjoint Set Union，是一种管理元素所属集合的数据结构。每次查询时把沿途的节点的父节点一并设置成全局父节点，从而达到均摊复杂度的超高效率（其中为的反阿克曼函数，可以看作为常数复杂度）。基于并查集的许多特性（包括好写），人们开发出了许多不同种类不同用途的并查集，其中就包括带边权的权值并查集和对元素进行分类的种类并查集。这篇文章将探讨这两种并查集的实现及相关应用。

权值并查集

在并查集的边上加上边权，每次查找父节点时把边权向上推送更新，从而达到类似于线段树 pushup 操作的效果。

UVA 11987 Almost Union-Find

题目地址：UVA 11987

题目难度：提高+/省选-

有个集合，次操作。规定第个集合里初始只有。有三种操作：

输入两个元素和，若和不在一个集合中，合并两个元素的集合。

输入两个元素和，若和不在一个集合中，把添加到所在的集合。

输入一个元素，查询所在集合的元素个数和所有元素之和。

输入格式：

有几组数据。

每组数据第一行输入和两个整数。

每组数据以下行，每行第一个数代表选择哪一个命令，若是或命令，则再输入两个整数和。若是，则输入一个整数。

输入文件结束符（EOF）结束输入。

输出格式：

输出行数为每组数据号命令的总数。

每一行输出两个整数和，即元素个数和元素和。

数据范围：

，。

原题面 PDF：Here

这道题在普通并查集维护所属集合的要求外，另外要求我们维护并查集的集合大小及元素总和，因此考虑权值并查集。基本思路是：在每次合并操作时，更新被插入集合父节点的 sum 与 size，累加上待插入集合的 sum 与 size 即可。特殊一点，对于移动操作（相当于把待插入集合变成一个大小为的单点）也是一样。

那么如何实现单点的移动呢？一般的思路是把点的父亲直接指向被插入集合的根，但这显然是错误的，因为：

当我们根据并查集的标准合并方式合并节点到树时，我们会把从属于号的号节点也一并接过去，这是我们不希望的，期望效果是只把送过去，只留下号一个在原位置。

那我们就需要提出一种建图方式，使得不直接与相连，但是要求又属于树。考虑为每个集合设置虚拟源点，初始时每个集合就是以虚拟源点为根，普通节点为叶子的两点集合。如此一来，移动操作就变成了下图：

然后就可以按照普通并查集的方法解了（因为创建了个虚拟源点，空间要开二倍）。

#include <bits/stdc++.h>

#define N 200010

using namespace std;

typedef long long ll;

int p[N], vol[N];
ll sum[N];

int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

void merge(int a, int b) {
    int u = find(a), v = find(b);
    p[u] = v;
    sum[v] += sum[u];
    vol[v] += vol[u];
}

void move(int a, int dest) {
    int u = find(a), v = find(dest);
    p[a] = v;
    vol[v]++;
    vol[u]--;
    sum[u] -= a;
    sum[v] += a;
}

bool related(int a, int b) {
    return find(a) == find(b);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n, m;
    while (cin >> n >> m) {
        for (int i = 1; i <= 2 * n; i++) {
            if (i <= n) {
                p[i] = i + n;
                vol[i] = 1;
                sum[i] = i;
            } else if (i > n) {
                p[i] = i;
                vol[i] = 1;
                sum[i] = i - n;
            }
        }
        while (m--) {
            int k, a, b;
            cin >> k;
            if (k == 1) {
                cin >> a >> b;
                if (!related(a, b)) merge(a, b);
            } else if (k == 2) {
                cin >> a >> b;
                if (!related(a, b)) move(a, b);
            } else {
                cin >> a;
                int u = find(a);
                cout << vol[u] << ' ' << sum[u] << endl;
            }
        }
    }
    return 0;
}

练习：P1196 [NOI2002] 银河英雄传说

种类并查集

一般的并查集可以用来维护一个带有传递性和连通性的集合，例如你亲戚的亲戚仍然是你的亲戚，普通并查集就可以做到维护你的所有亲戚和非亲戚，并判断某人是否是你的亲戚；而种类并查集则是它的升级，普通的并查集显然无法轻易维护诸如“敌人的敌人是朋友”的人际关系。这时，我们就可以多开几个普通的并查集用来维护不同类别之间的关系，即种类并查集。

P2024 [NOI2001] 食物链

题目地址：P2024

题目难度：普及+/提高

题目来源：NOI 2001

动物王国中有三类动物，这三类动物的食物链构成了有趣的环形。吃，吃，吃。

现有个动物，以编号。每个动物都是中的一种，但是我们并不知道它到底是哪一种。

有人用两种说法对这个动物所构成的食物链关系进行描述：

第一种说法是 1 X Y，表示和是同类。

第二种说法是2 X Y，表示吃。

此人对个动物，用上述两种说法，一句接一句地说出句话，这句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。

当前的话与前面的某些真的话冲突，就是假话；

当前的话中或比大，就是假话；

当前的话表示吃，就是假话。

你的任务是根据给定的和句话，输出假话的总数。

输入格式：

第一行两个整数，，表示有个动物，句话。

第二行开始每行一句话（按照题目要求，见样例）

输出格式：

一行，一个整数，表示假话的总数。

数据范围：

对于全部数据，，。

这道题是种类并查集的经典应用之一，用来判断一个不等式组是否有冲突矛盾。之前在讲Floyd 传递闭包的时候，我们就介绍了用传递闭包求解不等式组解的情况的方法。但是这种基于算法的解法，其时间复杂度是恐怖的，在这道题里显然会超时，我们转而使用种类并查集来解决这道题。

整理一下题面，把这些动物分成三类——“国王”、“大臣”和“平民”。国王统治大臣、大臣压榨平民、平民推翻国王。但是关键是我们不知道动物的初始分类，因此我们在每一类里都放上个节点。

然后，对于操作 ——可能出现的矛盾是：二者不为同类，这里却归为同类；对于操作，可能出现的是：倒反天罡（大臣搞国王、平民踩大臣）、自残（自己吃自己）。换句话说，如果某个节点的根指到其他区域，那么这两个动物在当前信息下不可能成为同类；如果不满足镇压关系的二者共用同一个根，显然也不成立。

根据并查集所带的实际意义判断即可。注意如果当前命题是正确的，不要忘记合并到并查集里。

#include <bits/stdc++.h>

#define N 50010
using namespace std;

int p[N * 3];
int n;

int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

void merge(int a, int b) {
    p[find(a)] = find(b);
}

bool related(int a, int b) {
    return find(a) == find(b);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int k, ans = 0;
    cin >> n >> k;
    for (int i = 1; i <= 3 * n; i++) p[i] = i;
    while (k--) {
        int op, x, y;
        cin >> op >> x >> y;
        if (x > n || y > n) ans++;
        else if (op == 1) {
            if (related(x + n, y) || related(x, y + n)) ans++;
            else {
                merge(x, y);
                merge(x + n, y + n);
                merge(x + 2 * n, y + 2 * n);
            }
        } else {
            if (related(x, y) || related(x, y + n)) ans++;
            else {
                merge(x, y + 2 * n);
                merge(x + n, y);
                merge(x + 2 * n, y + n);
            }
        }
    }
    cout << ans << endl;
    return 0;
}

练习：P1955 [NOI2015] 程序自动分析