$$\color{Red}{食物链量 简单通透 三种语言}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

思路

《食物链》 ——> 连接异祖宗的等式关键

d[x]此时只是到p[x]的距离，而d[px]应该当作已经正确的答案去反推:如 x吃y，d[x] + d[px] = d[y] + 1 故：d[px] = d[y] - d[x] + 1

还是设 d[x] 表示 x 与 px[x] 的关系，0 代表是同类，1 代表是x吃px[x], 根据关系图自然2就代表x被px[x]吃

java

import java.util.*;

public class Main {
    static int N = 50010;
    static int p[] = new int [N], d[] = new int[N];

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

    public static void main(String [] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), k = sc.nextInt();
        int res = 0;
        for (int i=1; i<=n; i++) p[i] = i;

        while (k -- > 0) {
            int op = sc.nextInt(), a = sc.nextInt(), b = sc.nextInt();
            if (a > n || b > n) res ++;
            else if (op == 1){
                    int pa = find(a), pb = find(b);
                    if (pa == pb && ((d[a] - d[b] + 3) % 3 != 0)) res ++;
                    else if (pa != pb){
                        p[pa] = pb;
                        d[pa] = d[b] - d[a];
                    }
            }
            else if (op == 2){
                int pa = find(a), pb = find(b);
                if (pa == pb && ((d[a] - d[b] - 1 + 3)%3 !=0)) res++;
                else if (pa != pb){
                    p[pa] = pb;
                    d[pa] = d[b] - d[a] + 1;
                }
            }
        }
        System.out.println(res);
    }
}

python3 代码

def find(x):
    if p[x] != x:
        t = find(p[x])
        d[x] += d[p[x]]
        p[x] = t
    return p[x]

N = 50010
d = [0] * N
p = [int(x) for x in range(N)]
res = 0
n, k = map(int, input().split())

for i in range(k):
    op, x, y = map(int, input().split())
    if x > n or y > n:  res += 1
    else:
        px, py = find(x), find(y)
        if op == 1:
            if px == py and (d[x] - d[y] + 3) % 3:
                res += 1

            elif px != py:
                p[px] = py
                d[px] = d[y] - d[x]
        else:
            if px == py and (d[x] - d[y] - 1 + 3) % 3:
                res += 1
            elif px != py:
                p[px] = py
                d[px] = d[y] - d[x] + 1

print(res)

C++ 代码

#include <iostream>
using namespace std;

const int N = 1e5 + 10;
int p[N], d[N];

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

int main()
{
    int n, k;
    cin >> n >> k;
    for(int i=0; i<n; i++)  p[i] = i;
    int res = 0, t, x, y;
    while(k--)
    {
        scanf("%d%d%d", &t, &x, &y);
        if(x > n || y > n)  res++;
        else
        {
            int px = find(x), py = find(y);
            if(t == 1)
            {
                //差值模3为0时，表明是同类
                if(px == py && (d[x] - d[y]) % 3)   res++;
                else if(px != py)
                {
                    p[px] = py;
                    d[px] = d[y] - d[x];
                }
            }
            else
            {
                //差值模3为1，代表x吃y,写为差值减一模0，当x吃y时
                //模3必为0，为其他值代表为假话
                if(px == py && (d[x] - d[y] - 1) % 3)   res++;
                else if(px != py)
                {
                    p[px] = py;
                    d[px] = d[y] - d[x] + 1;
                }
            }
        }
    }
    cout << res;
    return 0;
}