食物链

题目链接：https://ac.nowcoder.com/acm/problem/16884
刚看到这道题的时候听懵逼的，只能看出来是并查集，但觉得要加上权值做法很复杂 ，后来听毛毛雨姐姐讲完课以后顿悟了，只要将n的数量级开三倍，来表示三个层次就能解决问题，简化了不少。
思路：
将数组开3倍大，a表示自身的一层（即a类），a+n表示被a吃掉的一类，a+2n表示能吃a的一类。
判断一个语句是否为真，则只要判断它的反例是否成立。如 1 A B，表示A 和B 是一类的 那么只要判断A和B+n或者A和b+2n是不是一类的 如果是，说明这句话是假话，否则就是真话。
并查集的基本操作merge（归并） 和find 就不多说了。
具体细节看代码以及代码中的注释吧：

#include<iostream>
#include<algorithm>
#include<queue>
#include<string>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<stack>
#include<set>
#include<map>
#define ll long long
using namespace std;
#define close_stdin  ios::sync_with_stdio(false)
const int maxn = 50000;
int n, k;
int d, x, y,ans=0;
int fa[3 * maxn + 50];
int find(int x) {
    return (x == fa[x] ? x : fa[x]=find(fa[x]));
}
void my_merge(int x,int y){  // 将两种动物归并到一类中
    fa[find(x)] = find(y);

}
void my_input() {            //初始化 fa数组 使得每个人一开始为孤立的 以便后续建立关系
    cin >> n >> k;
    for (int i = 1;i <= 3 * n;i++) { fa[i] = i; }
}
void solve() {
    for (int i = 1;i <= k;i++) {
        cin >> d >> x >> y;
        if (x > n || y > n) { ans++;continue; }
        else if (d == 1) {
            if (find(x) == find(y + n) || find(x) == find(y + 2 * n)) { ans++;continue; } //x和y是同类  所以x和y必须在同层 否则就是假话
            my_merge(x, y);
            my_merge(x + n, y + n);
            my_merge(x + 2 * n, y + 2 * n);
        }
        else {
            if (find(x) == find(y) || find(x) == find(y + 2 * n)) { ans++;continue; }  // x吃y 所以 x在第一层 y在第二层 或者 x在第二层 y在第三层 或者x在第三城 y在第一层 否则是假话
            my_merge(x, y + n);
            my_merge(x+n, y +2* n);
            my_merge(x+2*n, y );
        }
    }
    cout << ans << "\n";
}
int main() {
    close_stdin;
    my_input();
    solve();
}