【洛谷】P2024 [NOI2001] 食物链

题目链接：P2024 [NOI2001] 食物链

思路

本题可以使用“扩展域并查集”的方法来解决，即把每个节点拆成三种角色（本体、吃的、被吃的）来模拟三种关系。也可以使用“带权并查集”方法，通过设置每个节点到其父节点的相对关系来处理三种状态。

代码

扩展域并查集

#define maxn 50010
#define maxm 100010
#include<bits/stdc++.h>
using namespace std;

int n, k;
int pre[maxn * 3], r[maxn * 3];

int ans = 0;

int find(int x) {
    return x == pre[x] ? x : pre[x] = find(pre[x]);
}

bool join(int x, int y) {
    int rx = find(x), ry = find(y);
    if (rx == ry) {
        return false;
    }
    if (r[rx] < r[ry])
        pre[rx] = ry;
    else {
        pre[ry] = rx;
        if (r[rx] == r[ry])
            r[rx]++;
    }
    return true;
}

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n * 3; i++)
        pre[i] = i;
    while (k--) {
        int opt, x, y;
        cin >> opt >> x >> y;
        if (x > n || y > n) {
            ans++;
        } else if (opt == 1) {
            if (find(x) == find(y + n) || find(x) == find(y + n + n)) {
                ans++;
                continue;
            }
            join(x, y);
            join(x + n, y + n);
            join(x + n + n, y + n + n);
        } else {
            if (x == y || find(x) == find(y) || find(x) == find(y + n + n)) {
                ans++;
                continue;
            }
            join(x, y + n);
            join(x + n, y + n + n);
            join(x + n + n, y);
        }
    }
    cout << ans << endl;
}

带权并查集

#define maxn 50010
#define maxm 100010
#include<bits/stdc++.h>
using namespace std;

int n, k;

int pre[maxn], sz[maxn];

int find(int x) {
    if (pre[x] != x) {
        int fa = pre[x];
        pre[x] = find(pre[x]);
        sz[x] = (sz[fa] + sz[x]) % 3;
    }
    return pre[x];
}

bool join(int x, int y, int w) {
    int rx = find(x), ry = find(y);
    if (rx == ry)
        return (sz[x] - sz[y] + 3) % 3 == w;
    pre[rx] = ry;
    sz[rx] = (sz[y] - sz[x] + w + 3) % 3;
    return true;
}

int ans = 0;

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        pre[i] = i;
    for (int i = 1; i <= k; i++) {
        int opt, x, y;
        cin >> opt >> x >> y;
        if (x > n || y > n)
            ans++;
        else if (opt == 1) {
            if (!join(x, y, 0)) {
                ans++;
            }
        } else {
            if (x == y || !join(x, y, 1)) {
                ans++;
            }
        }
    }
    cout << ans << endl;
    return 0;
}