食物链

中文题，题意没什么好说的。

和这题一样，可以手写逻辑，但是需要手写个逻辑，太麻烦了。

解决本题有两种方案，一种是带权并查集，一种是完全合并，有些人觉得后者好理解，本菜鸡并不觉得，而且它还要开三倍空间，所以本篇选择带权并查集来解决本题，但是如果你想要学习这种方法，我推荐这篇博客。

带权的并查集有更加广阔的应用场景，且空间消耗小于完全合并的方案。所以完全值得你花时间学习。

注意向量的思维。

在这里，向量指的是“偏移量”，表示的是子节点与父节点之间的关系。
0表示与父节点属于同一种族；
1表示被父节点吃；
2表示吃父节点。

显然，路径上的0具备传递性。
下图我推导1和2的传递性，共推导了种传递情况，验证了路径压缩时，路径直接相加对3取模即可。

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 50010;
struct node {
    int pre;       //父节点
    int relation;  //与父节点之间的关系
} p[N];
int find(int x) {  //查找根结点
    int temp;
    if (x == p[x].pre) return x;
    temp = p[x].pre;  //路径压缩
    p[x].pre = find(temp);
    p[x].relation = (p[x].relation + p[temp].relation) % 3;  //关系域更新
    return p[x].pre;  //根结点
}
int main() {
    int n, k;
    int sum = 0;  //假话数量
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; ++i) {  //初始化
        p[i].pre = i;
        p[i].relation = 0;
    }
    int ope, a, b;
    for (int i = 1; i <= k; ++i) {
        scanf("%d%d%d", &ope, &a, &b);
        if (a > n || b > n || ope == 2 && a == b) sum++;
        else {
            int root1 = find(a);
            int root2 = find(b);
            if (root1 != root2) {  // 合并
                p[root2].pre = root1;
                // 此时 rootx->rooty = rootx->x + x->y + y->rooty
                p[root2].relation = (3 + p[a].relation + (ope - 1) - p[b].relation) % 3;
            } else {
                //验证x->y之间的偏移量是否与题中给出的d-1一致
                if (ope == 1 && p[a].relation != p[b].relation) sum++;
                else if (ope == 2 && (3 - p[a].relation + p[b].relation) % 3 != ope - 1)
                    sum++;
            }
        }
    }
    printf("%d\n", sum);
    return 0;
}