python/TangDou/AcWing/DisjointSet/240_DQ.cpp

#include <bits/stdc++.h>

using namespace std;

const int N = 50010;
const int M = 3;

/**
 带权并查集：
 (1)不管是同类，还是吃与被吃的关系，都把它们放到同一个链中去
 (2)还没有关联关系的两条链,是两条彼此独立的链
 (3)同一个链中动物关系用距离根结点的长度来描述: 0:同类，1：吃, 2:被吃
 通过上面的记录关系，就可以推理出任何两个节点的关系
 */

int n, m;
int p[N]; // 家族
int d[N]; // i结点到父结点的距离
int res;  // 假话的个数

// 带权并查集find模板
// ① 需要将原始并查集的find模板一拆为二
// ② 在拆分的两句话中间，增加更新到父节点距离的代码
int find(int x) {
    if (p[x] != x) {
        int t = find(p[x]);
        d[x] = (d[p[x]] + d[x]) % M; // 父亲到根据的距离+自己到父亲的距离=自己到根的距离
        p[x] = t;
    }
    return p[x];
}

int main() {
    cin >> n >> m;
    // 并查集初始化
    for (int i = 1; i <= n; i++) p[i] = i;

    // m个条件
    while (m--) {
        int t, x, y;
        cin >> t >> x >> y;
        // 如果出现x,y的序号，大于最大号，那么肯定是有问题，是假话
        if (x > n || y > n) {
            res++;
            continue;
        }
        // 祖先
        int px = find(x), py = find(y);

        if (t == 1) {                          // x,y同类
            if (px != py) {                    // 没有处理过 x,y的关系
                p[px] = py;                    // 记录x,y的关系，把两个链合并一下，px认py为家族族长
                d[px] = (d[y] - d[x] + M) % M; // x,y是同类，则d[px] + d[x]= 0 + d[y]
            } else if ((d[x] - d[y] + M) % M)  // 在同一个家族中，x,y同类,则d[x]=d[y],即d[x]-d[y]=0,不等于0，假话
                res++;
        }

        if (t == 2) {                              // x吃y
            if (px != py) {                        // 没有处理过x,y的关系
                p[px] = py;                        // 记录x,y的关系，把两个链合并一下，px认py为家族族长
                d[px] = (d[y] + 1 - d[x] + M) % M; // x吃y,则d[px]+d[x]-1=d[y]
            } else if ((d[x] - d[y] - 1 + M) % M)  // 在同一个家族中，x吃y,则d[x]-d[y]=1,即d[x]-d[y]-1=0，要是不等于0，假话
                res++;
        }
    }
    // 输出
    printf("%d\n", res);
    return 0;
}