本题是加权并查集模板题。

难度：提高+/省选-

题目描述

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

        现有 N 个动物，以 1 － 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 句话，输出假话的总数。

输入输出格式

输入格式：

        从 eat.in 中输入数据

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

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

输出格式：

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

输入输出样例

Sample input

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

Sample output

3

说明

        1 ≤ N ≤ 5 ∗ 10^4
        1 ≤ K ≤ 10^5

题解

        考察加权并查集。做法：按照每一句话进行操作，推出矛盾。
        并查集可以很好地处理相联性问题，在大多数情况下，这种关系是一定的。但是对于多种关系，正常的并查集就不能满足需求。加权并查集用于关系种类多于1时的情景。比如本题中有三个关系：同类、吃、被吃，并查集中的结点通过这三种关系中的任意一种联系起来，并用权值描述具体的关系种类。简单来说，普通并查集维护关系，加权并查集维护相对关系。
        权值通常描述该结点与父结点的关系。在路径压缩后结点指向根节点，这个法则同样成立，我们需要在路径压缩时修改结点关系值（毕竟父结点被修改了），修改模板如下：

1
2
3
4
5
6
int find(x) {
    if (father[x] == x)return x;
    int r = find(father[x]);//获得根结点，此时父结点以上通过递归调用已经指向了根结点并更新了关系
    //更新关系...
    return father[x] = r;
}

        如果父结点与根结点关系是a，子结点与父结点关系为b，那么子结点和根结点关系是可以求得的（需要具体分析）。另外加权并查集只能来维护传递关系唯一的情景。这句话的意思是，如果我们知道A是B的子结点，关系为a，B是C的子结点，关系为b，那么A与C的关系应该是确定而唯一的。这种性质可以使我们通过任意一个第三者判别两个结点的关系，这是加权并查集的原理（第三者就是通过B和A的关系以及B和C的关系来推断A与C的关系，B就是第三者）。关系传递唯一性保证了路径压缩是等价变形，并且在加权并查集的一个等价类中，保证了任意两点的关系都可以推断出来。
        简单概括如下：

  • 加权并查集的任意一个等价类中任意两点相对关系都可以确定；取两个点，分别来自两个不同等价类，它们的关系无法确定。也就是说，只有在一个等价类中的点对才可以确定关系。
  • 当等价类中任意一个点被具体化时，等价类中其余点都会根据关系具体化。

        对于本题，规定权值0表示子结点与父结点为同类，1表示子结点吃父结点，2表示子结点被父结点吃。
        这样的关系进行传递的话，是否具有唯一性？答案是肯定的，如果父结点被它的父结点吃（权值为2），而子结点又吃父结点（权值为1），那么子结点与父结点的父结点什么关系？显然是同类（权值为0）。其余情况都可以由此推断出来，把所有的情况全部列出，可以发现：

        显然关系的传递具有唯一性。
        题目解决起来就很容易了。首先初始化并查集，令所有点权值为0（自己与自己是同类），然后进行合并。
        如何合并呢？根据上文的讨论，如果将并查集的两个等价类用一条边（合并就是加边的过程）联系起来，那么这两个等价类成为一个等价类，其中所有点对关系就会确定了。如何加边成为问题的重点。
        在并查集中，合并通常是令其中一个等价类的根节点去作为另一个等价类根节点的子结点。我们只需要选择合适的关系就可以了。假设要合并x和y（x和y分属两个等价类）。
        路径压缩后，rela[x]是x到其根节点的关系，rela[y]是y到其根节点的关系，这时x与y的关系又已知（假设为p）。从上文的讨论中可见，如果x根节点与y根节点关系为q，那么：

        理解：x通过其根节点这个第三者和通过y这个第三者得到的与y根节点的关系应该是相同的。
        因此建立x根节点到y根节点的边，修改x根节点权值为(rela[y]+p-rela[x]+3)%3，便把两个等价类合并成一个等价类。
        问题来了：合并两个等价类会不会本身就会出现矛盾？或者说合并这两个等价类会不会使某些点对关系矛盾？答案是否定的。前文已经说明，只有一个等价类中的两两点对关系确定，但分属两个等价类中的点对一点关系都没有。在两个等价类上连一条边，权值为多少都不会出现矛盾。我们加了一条边，这本身就是在建立这两个等价类点对的相对关系。
        但是如果发现x和y就在一个等价类中，还需要合并吗？显然不需要，这时两点关系已经确定，再修改关系就真的会出现矛盾了。这时需要做的就是找到两点关系并判断，如果不符，则这句话是假话。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>

using namespace std;
int n, m, ans = 0, father[50005], rela[50005] = {0};

int find(int x) {
    if (father[x] == x)return x;
    int r = find(father[x]);
    rela[x] = (rela[father[x]] + rela[x]) % 3;
    return father[x] = r;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)father[i] = i;
    for (int i = 1; i <= m; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        if (y > n || z > n)ans++;
        else if (x == 2 && y == z)ans++;
        else {
            int fy = find(y), fz = find(z);
            if (fy != fz)father[fy] = fz, rela[fy] = (rela[z] - rela[y] + (x == 2) + 3) % 3;
            else {
                if (x == 1 && rela[y] != rela[z])ans++;
                else if (x == 2 && (1 + rela[z]) % 3 != rela[y])ans++;
            }
        }
    }
    cout << ans;
    return 0;
}