嗯...
题目链接：https://www.luogu.org/problemnew/show/P2024
这道题和团伙这道题的思想比较类似，都是一个数组分成几个集合，但这道题的思路更加混乱，建议没做过团伙的先做一下
（题目链接：https://www.luogu.org/problemnew/show/P1892 我的博客：https://www.cnblogs.com/New-ljx/p/10883425.html）
首先食物链中这道题我们一定要明白题意：
(1) 判断是假话的条件要找全，条件2，3比较好判断，但条件1比较复杂且比较零碎。
(2) 明白两个动物之间一共有几种关系——三种关系：同类，猎物，天敌
(3) 如何进行集合分类。
首先前面讲过一共有三种情况，所以我们就把 f 数组分成三份，1 ~ n 表示同类， n +1 ~ 2 * n 表示为猎物，2 * n + 1 ~ 3 * n 表示为天敌。然后我们分情况判断：
1.在一开始就判断 X，Y是否大于N
2.当说X，Y为同类的时候，首先要判断以前是否说过X是Y的猎物或X是Y的天敌，如果是，continue。如果不是，因为X和Y是同类，所以进行合并即可：X就是Y，X的天敌就是Y的天敌，X的猎物就是Y的猎物。
3.当说X吃Y的时候，首先要判断X和Y是否是同类，如果是，continue。并且判断X的天敌是否是Y，如果是，说明这句话就是假话，continue。如果上述情况都不是，那么X的同类是Y的天敌，X的猎物是Y的同类，X的天敌是Y的猎物（本题中最为难想的地方）。
AC代码：
#include<cstdio>
#include<iostream>
#include<algorithm> using namespace std; int f[];
int cnt; inline int read(){
int num = ;
char c = getchar();
while(c < '' || c > '') c = getchar();
while(c >= '' && c <= ''){
num = num * + c - '';
c = getchar();
}
return num;
} inline int find(int x){
if(f[x] != x)
f[x] = find(f[x]);
return f[x];
} inline void unity(int a, int b){
int aa = find(a), bb = find(b);
if(aa != bb){
f[aa] = bb;
}
} int main(){
int n = read(), k = read();
for(int i = ; i <= n * ; i++) f[i] = i;
for(int i = ; i <= k; i++){
int a = read(), x = read(), y = read();
if(x > n || y > n){
cnt++;
continue;
}
if(a == ){
if(find(x + n) == find(y) || find(x + * n) == find(y)){
cnt++;
continue;
}
unity(x, y); unity(x + n, y + n); unity(x + n * , y + n * );
}
if(a == ){
if(x == y){
cnt++;
continue;
}
if(find(x) == find(y) || find(x + * n) == find(y)){
cnt++;
continue;
}
unity(x, y + * n); unity(x + n, y); unity(x + * n, y + n);
}
}
printf("%d", cnt);
return ;
}
AC代码
