[数据结构与算法]食物链（扩展域并查集）

题目描述

食物链（扩展域并查集）
有三种动物，他们形成一个食物链。
现在给出一些语句，根据关系判断他们的真假

C++

• x本体
• x+n捕食域（它可以吃哪些动物）
• x+2n天敌域（哪些动物可以吃它）

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 5e4 + 10;
int n, k;
int p[N*3]; // 三倍大小，用于表示3种关系

int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

void merge(int a, int b) {
    p[find(a)] = find(b);
}

int main() {
    scanf("%d%d", &n, &k);
    
    for (int i = 1; i <= n*3; i++) p[i] = i;
    int ans = 0;
    while (k--) {
        int d, x, y;
        scanf("%d%d%d", &d, &x, &y);
        
        if (x > n || y > n) {
            ans++;
            continue;
        }
        if (d == 1) {  // xy同类
        	// y吃x或者x吃y，这两种情况则不符合xy同类，是假话
            if (find(x) == find(y+n) || find(x) == find(y+n*2)) ans++;
            else {
                merge(find(x), find(y)); // xy本体同类
                merge(find(x+n), find(y+n)); // xy的捕食域相同
                merge(find(x+2*n), find(y + 2*n)); // xy的天敌域也应相同
            }
        } else if (d == 2) { // x吃y
        	// xy相同（题目），xy是同类或者y吃x，这三种情况不符合
            if (x == y || find(x) == find(y) || find(x) == find(y+n)) ans++;
            else {
                merge(find(x+n), find(y)); // x吃y
                merge(find(x), find(y+2*n)); // y被x吃
                merge(find(x+2*n), find(y+n)); // z吃x（y的捕食对象是x的天敌，题目中的环关系）
            }
        } 
        
    }
    cout << ans << endl;
    
    return 0;
}

参考资料

AcWing 240. 食物链——秦同学