java---并查集算法_食物链（每日一道算法2022.8.17）

难度警告！今天的题思路比较复杂，涉及数学知识congruence class

每天一道算法居然已经一个月了啊，期间居然没断更哈哈
呼呼~算法基础课过去三分之一了，啊后面好像越来越难了呜呜呜，还能保持日更吗？哭了

题目
动物王国中有三类动物 A,B,C，这三类动物的食物链构成了有趣的环形。
A 吃 B，B 吃 C，C 吃 A。
现有 N 个动物，以 1∼N 编号。
每个动物都是 A,B,C 中的一种，但是我们并不知道它到底是哪一种。
有人用两种说法对这 N 个动物所构成的食物链关系进行描述：

1.第一种说法是 1 X Y，表示 X 和 Y 是同类
2.第二种说法是 2 X Y，表示 X 吃 Y
3.此人对 N 个动物，用上述两种说法，一句接一句地说出 K 句话，这 K 句话有的是真的，有的是假的

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

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

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

输入
100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5
1
2
3
4
5
6
7
8
9

输出
3
1
2

public class 并查集_食物链 {
    //初始化，p代表所有的集，d代表到根节点的距离
    public static int N = 100010;
    public static int[] p = new int[N], d = new int[N];

    public static void main(String[] args) throws IOException{
        //初始化，p数组中初始根节点都指向自己，d初始都为0即可
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String[] init_data = in.readLine().split(" ");
        int n = Integer.parseInt(init_data[0]), m = Integer.parseInt(init_data[1]);
        for (int i = 1; i<=n; i++) {p[i] = i;}

        //res代表假话数量初始为1
        int res = 0;
        //操作区域
        while (m-- > 0){
            String[] data_arr = in.readLine().split(" ");
            int t = Integer.parseInt(data_arr[0]), x = Integer.parseInt(data_arr[1]), y = Integer.parseInt(data_arr[2]);

            //三条规则之一，x或y大于n，假
            if (x > n || y > n) {res++;}
            else {
                int px = find(x), py = find(y);

                //t=1判断x和y是不是同类
                if (t == 1) {
                    //首先判断x和y是不是在一颗树上，在一颗树上并且x到根节点的距离%3和y到根节点的距离%3相等，说明是同类，反之不是
                    if (px==py && (d[x]-d[y])%3 != 0){res++;}
                    //如果不在一颗树上，那说明这句话必定是真话，xy是同类，将x树和y树合在一起，让x的根节点指向y的根节点
                    //而此时我们不知道d[px]是该设为多少
                    //但我们知道xy是同类那他们到根节点的距离%3是相等的，也就是d[x] + d[px] ≡ d[y]，就能得知d[y]-d[x] = d[px]
                    //这里涉及数学知识congruence class，感兴趣可以查一查
                    else if (px!=py) {
                        p[px] = py;
                        d[px] = d[y] - d[x];
                    }
                }
                //t=2判断x能不能吃y
                else if (t == 2) {
                    //判断x和y在不在一棵树上，在一棵树上同时x到根节点的距离+1如果和y到根节点的距离相等，说明x可以吃y，反之不是
                    if (px==py && (d[x]-d[y]-1)%3 != 0) {res++;}
                    //不在一棵树上说明是真话，x能吃y，x%3应该比y%3大1
                    //然后设置d[px]的距离，道理和上面相同，只不过这次是d[x] - 1 + d[px] ≡ d[y], 也就是d[y]-d[x]+1 = d[px]
                    else if (px!=py) {
                        p[px] = py;
                        d[px] = d[y]+1-d[x];
                    }
                }
            }
        }

        System.out.println(res);
    }

    //并查集的查找
    public static int find(int x) {
        if (p[x]!=x) {
            //切记这里是先拿到上一个元素，然后加上上一个元素到根节点的距离，这样最后我们就得到了x到根节点的距离
            int t = find(p[x]);
            d[x] += d[p[x]];
            //最后进行并查集的优化，让所有点都直接指向根节点
            p[x] = t;
        }
        return p[x];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

就拿题目作为例子
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5
第一次为假，因为101大于给定数100
第二次为真，1吃2
第三次为真，2吃3
第四次为假，3不能吃3，同类不能吃同类
第五次为假，1和3不是同类
第六次为真，3可以吃1
第七次为真，5和5是同类
最后输出假话次数3

这里其实有个很有意思的点，就是给定的条件里并没有告诉我们3能吃1，但我们根据1->2->3,食物链需要形成闭环，那么就可以推断出3->1

用并查集实现这道题的思路就是，我们以当前点到根节点的距离%3的结果来判断当前点的种类，因为%3只有3k,3k+1,3k+2,三种可能，这样我们就能知道如果x%3和y%3相等，那么他们的种类是一样的，如果x%3和y-1%3相等，代表x吃y，例如x=1,y=2, 1%3=2-1%3

声明：算法思路来源为y总，详细请见https://www.acwing.com/
本文仅用作学习记录和交流