02 种类并查集

种类并查集

一般的并查集，维护的是具有连通性、传递性的关系，例如亲戚的亲戚是亲戚。但是，有时候，我们要维护另一种关系：敌人的敌人是朋友。种类并查集就是为了解决这个问题而诞生的。

我们先来看一个例题：

（洛谷P1525 关押罪犯）

[NOIP2010 提高组] 关押罪犯

题目背景

NOIP2010 提高组 T3

题目描述

S 城现有两座监狱，一共关押着 $N$ 名罪犯，编号分别为 $1\sim N$。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。我们用“怨气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之间的积怨越多。如果两名怨气值为 $c$ 的罪犯被关押在同一监狱，他们俩之间会发生摩擦，并造成影响力为 $c$ 的冲突事件。

每年年末，警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表，然后上报到 S 城 Z 市长那里。公务繁忙的 Z 市长只会去看列表中的第一个事件的影响力，如果影响很坏，他就会考虑撤换警察局长。

在详细考察了 $N$ 名罪犯间的矛盾关系后，警察局长觉得压力巨大。他准备将罪犯们在两座监狱内重新分配，以求产生的冲突事件影响力都较小，从而保住自己的乌纱帽。假设只要处于同一监狱内的某两个罪犯间有仇恨，那么他们一定会在每年的某个时候发生摩擦。

那么，应如何分配罪犯，才能使 Z 市长看到的那个冲突事件的影响力最小？这个最小值是多少？

输入格式

每行中两个数之间用一个空格隔开。第一行为两个正整数 $N,M$，分别表示罪犯的数目以及存在仇恨的罪犯对数。接下来的 $M$ 行每行为三个正整数 $a_j,b_j,c_j$，表示 $a_j$ 号和 $b_j$ 号罪犯之间存在仇恨，其怨气值为 $c_j$。数据保证 $1<a_j\leq b_j\leq N, 0 < c_j\leq 10^9$，且每对罪犯组合只出现一次。

输出格式

共一行，为 Z 市长看到的那个冲突事件的影响力。如果本年内监狱中未发生任何冲突事件，请输出 0。

样例 #1

样例输入 #1

4 6
1 4 2534
2 3 3512
1 2 28351
1 3 6618
2 4 1805
3 4 12884

样例输出 #1

3512

提示

输入输出样例说明

罪犯之间的怨气值如下面左图所示，右图所示为罪犯的分配方法，市长看到的冲突事件影响力是 $3512$（由 $2$ 号和 $3$ 号罪犯引发）。其他任何分法都不会比这个分法更优。

数据范围

对于 $30\%$ 的数据有 $N\leq 15$。

对于 $70\%$ 的数据有 $N\leq 2000,M\leq 50000$。

对于 $100\%$ 的数据有 $N\leq 20000,M\leq 100000$。

我们开一个两倍大小的并查集。例如，假如我们要维护4个元素的并查集，我们改为开8个单位的空间：

我们用1_{4维护**朋友**关系（就这道题而言，是指关在同一个监狱的狱友），用5}8维护敌人关系（这道题里是指关在不同监狱的仇人）。现在假如我们得到信息：1和2是敌人，应该怎么办？

我们merge(1, 2+n), merge(1+n, 2);。这里n就等于4，但我写成n这样更清晰。对于1个编号为i的元素，i+n是它的敌人。所以这里的意思就是：1是2的敌人，2是1的敌人。

现在假如我们又知道2和4是敌人，我们merge(2, 4+n), merge(2+n, 4);：

发现了吗，敌人的敌人就是朋友，2和4是敌人，2和1也是敌人，所以这里，1和4通过2+n这个元素间接地连接起来了。这就是种类并查集工作的原理。

#include <cstdio>
#include <cctype>
#include <algorithm>
int read() //快速读入，可忽略
{
    int ans = 0;
    char c = getchar();
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c))
    {
        ans = (ans << 3) + (ans << 1) + c - '0';
        c = getchar();
    }
    return ans;
}
struct data  //以结构体方式保存便于排序
{
    int a, b, w;
} C[100005];
int cmp(data &a, data &b)
{
    return a.w > b.w;
}
int fa[40005], rank[40005];  //以下为并查集
int find(int a)
{
    return (fa[a] == a) ? a : (fa[a] = find(fa[a]));
}
int query(int a, int b)
{
    return find(a) == find(b);
}
void merge(int a, int b)
{
    int x = find(a), y = find(b);
    if (rank[x] >= rank[y])
        fa[y] = x;
    else
        fa[x] = y;
    if (rank[x] == rank[y] && x != y)
        rank[x]++;
}
void init(int n)
{
    for (int i = 1; i <= n; ++i)
    {
        rank[i] = 1;
        fa[i] = i;
    }
}
int main()
{
    int n = read(), m = read();
    init(n * 2); //对于罪犯i，i+n为他的敌人
    for (int i = 0; i < m; ++i)
    {
        C[i].a = read();
        C[i].b = read();
        C[i].w = read();
    }
    std::sort(C, C + m, cmp);
    for (int i = 0; i < m; ++i)
    {
        if (query(C[i].a, C[i].b))  //试图把两个已经被标记为“朋友”的人标记为“敌人”
        {
            printf("%d\n", C[i].w); //此时的怒气值就是最大怒气值的最小值
            break;
        }
        merge(C[i].a, C[i].b + n);
        merge(C[i].b, C[i].a + n);
        if (i == m - 1)  //如果循环结束仍无冲突，输出0
            puts("0");
    }
    return 0;
}

刚才我说，种类并查集可以维护敌人的敌人是朋友这样的关系，这种说法不够准确，较为本质地说，种类并查集（包括普通并查集）维护的是一种循环对称的关系。

所以如果是三个及以上的集合，只要每个集合都是等价的，且集合间的每个关系都是等价的，就能够用种类并查集进行维护。例如下面这道题：

[NOI2001] 食物链

题目描述

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

现有 $N$ 个动物，以 $1 \sim N$ 编号。每个动物都是 $A,B,C$ 中的一种，但是我们并不知道它到底是哪一种。

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

• 第一种说法是 1 X Y，表示 $X$ 和 $Y$ 是同类。
• 第二种说法是2 X Y，表示 $X$ 吃 $Y$。

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

• 当前的话与前面的某些真的话冲突，就是假话；
• 当前的话中 $X$ 或 $Y$ 比 $N$ 大，就是假话；
• 当前的话表示 $X$ 吃 $X$，就是假话。

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

输入格式

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

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

输出格式

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

样例 #1

样例输入 #1

100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5

样例输出 #1

3

提示

对于全部数据，$1\le N\le 5 \times 10^4$，$1\le K \le 10^5$。

于是我们可以用一个三倍大小的并查集进行维护，用i+n表示i的捕食对象，而i+2n表示i的天敌。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
#define int long long
const int N = 3e5 + 5;
int fa[N];
int n, k;
int find(int x)
{
    if (fa[x] != x)
    {
        fa[x] = find(fa[x]);
    }
    return fa[x];
}
void merge(int x, int y)
{
    int r1 = find(x), r2 = find(y);
    if (r1 != r2)
        fa[r1] = r2;
}
bool question(int x, int y)
{
    return find(x) == find(y);
}
void init()
{
    for (int i = 1; i <= 3 * n; i++)
        fa[i] = i;
}
signed main()
{
    scanf("%d %d", &n, &k);
    init();
    int oper, x, y, ans = 0;
    for (int i = 1; i <= k; i++)
    {
        scanf("%d %d %d", &oper, &x, &y);
        if (x > n || y > n)
            ans++;
        else if (oper == 1)
        {
            if (question(x + n, y) || question(x + 2 * n, y))
            {
                ans++;
            }
            else
            {
                merge(x, y);
                merge(x + n, y + n);
                merge(x + 2 * n, y + 2 * n);
            }
        }
        else if (oper == 2)
        {
            if (question(x, y) || question(x, y + n))
            {
                ans++;
            }
            else
            {
                merge(x + n, y);
                merge(x + 2 * n, y + n);
                merge(x, y + 2 * n);
            }
        }
    }
    cout << ans << endl;
    return 0;
}