嗯...

 

题目链接：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代码：

1 #include
      
        2 #include
       
         3 #include
        
          4  5 using namespace std; 6  7 int f[1000005]; 8 int cnt; 9 10 inline int read(){11     int num = 0;12     char c = getchar();13     while(c < '0' || c > '9') c = getchar();14     while(c >= '0' && c <= '9'){15         num = num * 10 + c - '0';16         c = getchar();17     }18     return num;19 }20 21 inline int find(int x){22     if(f[x] != x)23         f[x] = find(f[x]);24     return f[x];25 }26 27 inline void unity(int a, int b){28     int aa = find(a), bb = find(b);29     if(aa != bb){30         f[aa] = bb;31     }32 }33 34 int main(){35     int n = read(), k = read();36     for(int i = 1; i <= n * 3; i++) f[i] = i;37     for(int i = 1; i <= k; i++){38         int a = read(), x = read(), y = read();39         if(x > n || y > n){40             cnt++;41             continue;42         }43         if(a == 1){44             if(find(x + n) == find(y) || find(x + 2 * n) == find(y)){45                 cnt++;46                 continue;47             }48             unity(x, y); unity(x + n, y + n); unity(x + n * 2, y + n * 2);49         }50         if(a == 2){51             if(x == y){52                 cnt++;53                 continue;54             }55             if(find(x) == find(y) || find(x + 2 * n) == find(y)){56                 cnt++;57                 continue;58             }59             unity(x, y + 2 * n); unity(x + n, y); unity(x + 2 * n, y + n);60         }61     }62     printf("%d", cnt);63     return 0;64 }