题目链接：[NOI2001] 食物链 - 洛谷​​​​​​

题目链接：1182 -- 食物链 

注：poj那题需要用scanf 和printf 

题面： 

 于这篇博客的时候我也不是很清楚种类并查集是什么，我只知道这个可以解决敌人的敌人是朋友的问题

这题将动物分成三个种类（A， B， C）,A->B,B->C,C->A,那么就可以分为3个种类：1-n为自身，n+1-2n为食物，2n+1-3n为天敌。

题目让我们求假话的数量。

假话的判定：

• 当前的话与前面的某些真的话冲突，就是假话
• 当前的话中 X 或 Y 比 N 大，就是假话
• 当前的话表示 X 吃 X，就是假话

由此我们很容易的写出a > n || b > n的时候ans++，

if(f == 2 && a == b)ans++;

然后就是冲突问题了：如果a和b的同类，那么a的天敌就不能是b，a的食物也不能是b；

如果a的食物是b，那么a的同类不能是b（可以和上述a == b合并），a的天敌也不能是b

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <set>
#include <queue>
#include <stack>
using namespace std;
#define endl "\n"
#define pi pair<int, int>
#define ll long long
#define N 150005
int s[N];
int findx(int x){
    if(s[x] == x){
        return x;
    }
    return s[x] = findx(s[x]);
}
bool check(int x, int y){
    return findx(x) == findx(y);
}
void merge(int x, int y){
    int fx = findx(x);
    int fy = findx(y);
    if(fx != fy){
        s[fy] = fx;
    }
}
int main(){
    int n, k;
    cin >> n >> k;
    for(int i = 1; i <= n * 3; i++){
        s[i] = i;
    }
    int ans = 0;
    for(int i = 0; i < k; i++){
        int flag, a, b;
        cin >> flag >> a >> b;
        if(a > n || b > n){
            ans ++;
            continue;
        }
        if(flag == 1){
            if(check(a + n, b) || check(a + 2 * n, b)){
                ans++;
            }else{
                merge(a, b), merge(a + n, b + n), merge(a + 2 * n, b + 2 * n);
            }
        }else{
            if(check(a, b) || check(a + 2 * n, b)){
                ans++;
            }else{
                merge(a, b + 2 * n), merge(a + n, b), merge(a + 2 * n, b + n);
            }
        }
    }
    cout << ans << endl;
    return 0;
}

poj：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <set>
#include <queue>
#include <stack>
using namespace std;
#define endl "\n"
#define pi pair<int, int>
#define ll long long
#define N 150005
int s[N];
int findx(int x){
    if(s[x] == x){
        return x;
    }
    return s[x] = findx(s[x]);
}
bool check(int x, int y){
    return findx(x) == findx(y);
}
void merge(int x, int y){
    int fx = findx(x);
    int fy = findx(y);
    if(fx != fy){
        s[fy] = fx;
    }
}
int main(){
    int n, k;
    scanf("%d %d", &n, &k);

        for (int i = 1; i <= n * 3; i++) {
            s[i] = i;
        }
        int ans = 0;
        for (int i = 0; i < k; i++) {
            int flag, a, b;
            scanf("%d %d %d", &flag, &a, &b);
            if (a > n || b > n) {
                ans++;
                continue;
            }
            if (flag == 1) {
                if (check(a + n, b) || check(a + 2 * n, b)) {
                    ans++;
                } else {
                    merge(a, b), merge(a + n, b + n), merge(a + 2 * n, b + 2 * n);
                }
            } else {
                if (check(a, b) || check(a + 2 * n, b)) {
                    ans++;
                } else {
                    merge(a, b + 2 * n), merge(a + n, b), merge(a + 2 * n, b + n);
                }
            }
        }
        printf("%d\n", ans);

    return 0;
}