食物链

带权并查集

写法一:

#include<iostream>
#define N 51000
using namespace std;

int p[N],d[N];

int find(int x)
{
    if(p[x] == x)   return x;
    int u = find(p[x]);
    d[x] += d[p[x]];
    p[x] = u;
    return u;
}

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

    for(int i = 0;i <= n;i ++)  p[i] = i;

    int res = 0;
    for(int i = 0;i < k;i ++)
    {
        int t,a,b;
        scanf("%d%d%d",&t,&a,&b);
        if(a > n || b > n)  res ++;
        else if(t == 2 && a == b)   res ++;
        else
        {
            //关系设定:
            int rel;
            if(t == 2)  rel = 1;
            else rel = 0;

            int x = find(a) , y = find(b);
            if(x == y)
            {
                if( ( ( (d[a] - d[b]) % 3) + 3 ) % 3 != rel)
                    res ++;
            }
            else
            {
                p[x] = y;
                d[x] = d[b] - (d[a] - rel);
            }
        }
    }
    printf("%d",res);
}

写法二:

#include<iostream>

using namespace std;
const int N = 5e4 + 10;
int p[N], d[N];

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

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) p[i] = i;
    int res = 0;
    while (m--) {
        int t, x, y;
        scanf("%d%d%d", &t, &x, &y);

        if (x > n || y > n) res++;
        else {
            int px = find(x), py = find(y);
            if (t == 1) {
                if (px == py && (d[y] - d[x]) % 3) res++;
                else if (px != py) {
                    p[px] = py;
                    d[px] = d[y] - d[x];
                }
            } else if (t == 2) {
                if (px == py && (d[y] + 1 - d[x]) % 3) res++;
                else if (px != py) {
                    p[px] = py;
                    d[px] = d[y] + 1 - d[x];
                }
            }
        }
    }
    cout << res << endl;

    return 0;
}

具体图解可以参考 大佬的图解