食物链

算法思想

1. 利用扩展版并查集解决问题

扩展版并查集

• 在基本并查集的基础上，为每个节点 x 增加 d[x]属性
• d[x] 代表节点 x 与其父节点的距离（关系） d[x] % 3 = 0 代表 x 与父节点同类 d[x] % 3 = 1 代表 x 被父节点吃 d[x] % 3 = 2 代表 x 吃父节点

性质

根节点透视性

• 同一集合中的任意两个节点 x, y 的关系，都可以通过它们各自与根节点 r 的关系推导得出
• dx、 dy 分别表示节点 x 与根节点的距离（关系）和节点 y 与根节点的距离（关系）
• 若 (dx - dy) % 3 == 0，则它们是同类
• 若 (dx - 1 - dy) % 3 == 0，x 被 y 吃
• 若 (dx - 2 - dy) % 3 == 0，x 吃 y

算法模板

import java.util.*;
public class Main {
    static int N = 100010;
    static int[] p = new int[N];
    // d[i]代表第 i 个节点到根节点的距离
    // 第 i 个节点的根节点发生变化后，d[i] 不会立即更新，
    // 而会在下次查找第 i 个节点时更新
    static int[] d = new int[N];


    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int count = 0;
        for(int i = 0; i <= n; i ++) p[i] = i;
        
        while(k -- > 0)
        {
            int t = in.nextInt();
            int x = in.nextInt();
            int y = in.nextInt();
            
            if(x > n || y > n) count ++;
            else
            {
                int rx = find(x), ry = find(y);
                if(t == 1)
                {
                    if(rx == ry && ((d[x] - d[y]) % 3) != 0) count ++;
                    else if(rx != ry)
                    {
                        p[rx] = ry;
                        // (d[y] - d[x] - d[rx]) % 3 == 0
                        // d[rx] = d[y] - d[x] + i * 3, i 取任意值，其意义不变
                        d[rx] = d[y] - d[x];
                    }
                }
                else
                {
                    if(x == y) count ++;
                    else
                    {
                        if(rx == ry && (d[x] - d[y] - 1) % 3 != 0) count ++;
                        else if(rx != ry)
                        {
                            p[rx] = ry;
                            // (d[y] - d[x] - d[rx] ) % 3 == 1
                            // d[rx] = d[y] - d[x] + 1 + i * 3, i 取任意值，其意义不变
                            d[rx] = d[y] - d[x] + 1;
                        }
                    }
                }
            }
        }

        
        System.out.println(count);
    }

    // 路径优化的并查集
    // 集合对应的树的层级最多有三层
    // 并且会被自动优化为两级
    static int find(int x)
    {
        //递归标准写法
        if(p[x] == x) return p[x];
        else 
        {
            int r = find(p[x]);
            d[x] += d[p[x]];
            p[x] = r;
            return p[x];
        }
        // 简化写法
        // 不结束条件与递归体
        // if(p[x] != x)
        // {
        //     int r = find(p[x]);
        //     d[x] += d[p[x]];
        //     p[x] = r;
        // }
        // return p[x];
    }
}