题解 | #食物链#

建议列一个关系图

列出题目所给的关系图，对于一个物种x，有

那么为了列出这三种关系，我们需要将域扩大到原来的三倍（n*3）,定义x类，则x+n是它捕食的一类，x+2n是捕食它的一类

那么d == 1时,x与y+n，y+2n在同一层的话为矛盾

对于d == 2,我们将关系图补全

我们可以清晰看到x与y,yy不是同一类，如果出现这样的关系即为矛盾。 归并时按照图中关系归并即可。

下面是代码

/* NC16884 食物链 */
/* 2024.3.17 扩展域并查集*/
//开三倍的n，表示同类，被x吃的类，能吃x的类
#include<bits/stdc++.h>
using namespace std;
const int N = 5e4 + 10;
int n, k;
int fa[N*3];

int find(int x){
    return fa[x] == x ? x : find(fa[x]);
}

int main(){
    ios::sync_with_stdio(0);
    cin >> n >> k;
    for (int i = 1; i <= n*3; i++){
        fa[i] = i;
    }
    int res = 0;
    while(k--){
        int t, x, y;
        cin >> t >> x >> y;
        if(x > n || y > n){
            res++;
            continue;
        }
        int f1 = find(x);
        int f2 = find(y);
        int ff1 = find(x+n);
        int ff2 = find(y+n);
        int fff1 = find(x+n+n);
        int fff2 = find(y+n+n);
        if(t == 1){
            if(f1 == ff2 || f1 == fff2){ //同类必须在同层
                res++;
                continue;
            }
            fa[f1] = f2;
            fa[ff1] = ff2;
            fa[fff1] = fff2;
        }
        else if(t == 2){ //x吃y关系,y被吃层中x，x能吃层中y
            if(x == y || f1 == f2 || f1 == ff2) {//同城，关系倒转为错
                res++;
                continue;
            }
            //这是一个环形的食物链
            fa[f1] = fff2;
            fa[ff1] = f2;
            fa[fff1] = ff2;
        }
    }
    cout << res << "\n";
    return 0;
}