题目描述

食物链

思路.

用并查集创建 数据集合, 用一个d[] 数组维护每个节点到根节点的距离.
每两个点的距离, 为两个点mod 3 与根节点的数.
1 吃 根节点.
2 被根节点吃.
0 与 根节点同类.

JAVA 代码

import java.util.*;
import java.io.*;

class Main{
    static int N = 50010 , res = 0;

    //p[N] 并查集 -- d[N] 维护到根节点的距离
    static int[] p = new int[N], d = new int[N];

    // 模板
    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[])throws IOException{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String[] s = in.readLine().split(" ");
        int n = Integer.parseInt(s[0]);
        int k = Integer.parseInt(s[1]);

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


        while(k-->0){
            s = in.readLine().split(" ");
            int t = Integer.parseInt(s[0]);
            int x = Integer.parseInt(s[1]);
            int y = Integer.parseInt(s[2]);


            //如果大于范围则是说谎.
            if(x > n || y > n) res ++;
            else{
                //px,py是x,y的祖宗节点
                int px = find(x), py = find(y);
                if(t == 1){
                    //如果在一个集合里. 并且距离%3 不是0  那么则不是同类 说谎+1;
                    if(px == py && (d[x] - d[y]) % 3 !=0)res ++;
                    //为在集合里
                    else if(px!=py){
                        //添加到一个集合里.
                        p[px] = py;
                        //维护好距离.
                        d[px] = d[y] - d[x];
                    }
                }else{//t == 2
                    if(px == py && (d[x] - d[y] - 1) % 3 != 0) res++;
                    else if(px != py){
                        //(dx + ? - dy - 1) % 3 == 0 =>  ? = dy - dx + 1
                        p[px] = py;
                        d[px] = d[y] - d[x] + 1;
                    }
                }    
            }

        }
        System.out.println(res);

    }
}