食物链（扩展域）

洛谷-2024-食物链

分析

见《进阶指南》第201页。

实现

#include <iostream>
using namespace std;

const int N = 50010;
int f[3 * N];

int find (int x) {
    if (f[x] == x) return x;
    return f[x] = find(f[x]);
}
void merge (int x, int y) {
    f[find(x)] = find(y);
}
bool query (int x, int y) {
    return find(x) == find(y);
}

int main () {
    int n, m;
    scanf("%d%d", &n, &m);

    // [1 ~ n] 为同类域，[n+1 ~ 2n] 为猎物域，[2n+1 ~ 3n] 为天敌域
    for (int i = 1; i <= 3 * n; ++ i) f[i] = i;
    int res = 0;
    while (m --) {
        int opt, x, y;
        scanf("%d%d%d", &opt, &x, &y);
        if (x < 1 || x > n || y < 1 || y > n) {
            ++ res;
            continue;
        }

        if (opt == 1) {
            if (query(y, x + n) || query(y, x + 2 * n)) {
                ++ res;
                continue;
            }
            merge(x, y);
            merge(x + n, y + n);
            merge(x + 2 * n, y + 2 * n);
        } else {
            if (query(y, x) || query(y, x + 2 * n)) {
                ++ res;
                continue;
            }
            merge(x + n, y);
            merge(x + 2 * n, y + n);
            merge(x, y + 2 * n);
        }
    }
    printf("%d", res);
    return 0;
}