[poj1182] 食物链

题目链接

题意

??\(n(1\leq n\leq50000)\)只动物，编号为\(1,2,\cdots,n\)，属于A，B，C的一种。已知A吃B，B吃C，C吃A。给出以下两种信息\(k(1\leq k\leq100000)\)条。

1. x和y属于同一种
2. x吃y
   有一些是相互矛盾的，求不正确信息的条数。

题解

??并查集用于快速判断两个数是否同一集合与快速合并两个集合成一个集合并求出一些节点之间的关系，因此并查集是维护“属于同一组”的数据结构。本题巧妙利用\(\%3\)来判断捕食关系。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int N = 5e4 + 5, INF = 2e9;

int fa[N], r[N];

int find(int x) {
    if (x != fa[x]) {
        int fx = find(fa[x]);
        r[x] = (r[x] + r[fa[x]]) % 3; // 递归后计算
        fa[x] = fx; // 路径压缩
    }
    return fa[x];
}

bool Union(int type, int x, int y) {
    int fx = find(x);
    int fy = find(y);
    if (fx == fy) {
        if ((r[x] - r[y] + 3) % 3 != type) return 1;
        return 0;
    }
    fa[fx] = fy;
    r[fx] = (r[y] - r[x] + type + 3) % 3;
    return 0;
}

int main() 
{
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; ++i) fa[i] = i;
    int ans = 0;
    int d, x, y; 
    while (k--) {
        scanf("%d%d%d", &d, &x, &y);
        if (x > n || y > n || (x == y && d == 2)) ans++;
        else if (Union(d - 1, x, y)) ans++;
    }
    printf("%d\n", ans);
    return 0;
}

[poj1182] 食物链

原文：https://www.cnblogs.com/2inf/p/12803992.html