Acwing240食物链

题目

动物王国中有三类动物 A,B,C，这三类动物的食物链构成了有趣的环形。

A 吃 B，B 吃 C，C 吃 A

现有 N 个动物，以 1∼N 编号。

每个动物都是 A,B,C中的一种，但是我们并不知道它到底是哪一种。

有人用两种说法对这 N 个动物所构成的食物链关系进行描述：

第一种说法是 1 X Y，表示 X 和 Y 是同类。

第二种说法是 2 X Y，表示 X 吃 Y

此人对 N 个动物，用上述两种说法，一句接一句地说出 K 句话，这 K 句话有的是真的，有的是假的。

当一句话满足下列三条之一时，这句话就是假话，否则就是真话。

1. 当前的话与前面的某些真的话冲突，就是假话；
2. 当前的话中 X 或 Y 比 N 大，就是假话；
3. 当前的话表示 X 吃 X，就是假话。

你的任务是根据给定的 N 和 K 句话，输出假话的总数。

输入格式

第一行是两个整数 N 和 K，以一个空格分隔。

以下 K 行每行是三个正整数 D，X，Y两数之间用一个空格隔开，其中 D 表示说法的种类。

若 D=1，则表示 X 和 Y 是同类。

若 D=2，则表示 X 吃 Y

输出格式

只有一个整数，表示假话的数目。

数据范围

1≤N≤50000
0≤K≤100000

输入样例：

100 7
1 101 1 
2 1 2
2 2 3 
2 3 3 
1 1 3 
2 3 1 
1 5 5

输出样例：

3

代码

import java.util.Scanner;

public class Main {
    static int n, k, N = 50010;
    static int[] p = new int[N], dis = new int[N];

    // 并查集查找函数，查找元素x所在集合的根节点，并更新dis数组
    public static int find(int x) {
        if (p[x] != x) {
            // 递归查找x的根节点，并更新x到根节点的距离
            int t = find(p[x]);
            dis[x] += dis[p[x]];
            p[x] = t; // 路径压缩，将x的父节点直接指向根节点
        }
        return p[x];
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt(); // 人数
        k = in.nextInt(); // 事务数

        // 初始化并查集和距离数组
        for (int i = 1; i <= n; i++) {
            p[i] = i; // 初始化每个人的父节点为自己
        }

        int ans = 0; // 记录不能确定的事务数量
        while (k > 0) {
            k--;
            int d = in.nextInt(); // 事务类型
            int a = in.nextInt(); // 人a
            int b = in.nextInt(); // 人b

            // 若a或b超出人数范围，则该事务无效，直接跳过
            if (a > n || b > n) {
                ans++;
            } else {
                int pa = find(a); // 人a所在集合的根节点
                int pb = find(b); // 人b所在集合的根节点

                if (d == 1) { // 事务类型为1，表示a和b是同类关系
                    if (pa == pb && (dis[a] - dis[b]) % 3 != 0) ans++;
                    else if (pa != pb) { // 若a和b不在同一个集合中，则合并集合
                        p[pa] = pb; // 将a所在集合的根节点指向b所在集合的根节点
                        dis[pa] = dis[b] - dis[a]; // 更新a所在集合中元素到根节点的距离
                    }
                } else { // 事务类型为2，表示a是b的上级
                    if (pa == pb && (dis[a] - dis[b] - 1) % 3 != 0) ans++;
                    else if (pa != pb) { // 若a和b不在同一个集合中，则合并集合
                        p[pa] = pb; // 将a所在集合的根节点指向b所在集合的根节点
                        dis[pa] = dis[b] - dis[a] + 1; // 更新a所在集合中元素到根节点的距离
                    }
                }
            }
        }
        System.out.println(ans); // 输出不能确定的事务数量
    }
}