简单注释

仅仅为了记录一点关键点！

负数取余处理.cpp

#include <iostream>

using namespace std;

int main()
{
    cout << -8 % 3 << endl;
    // x % 3 != y % 3 -> 由于负数问题可能会错
    cout << -5 % 3 << " " << 4 % 3 << endl; // -2 1
    // 改为 (x - y) % 3
    cout << (-5 - 4) % 3 << endl; // 0
    // 或者 (x % 3 + 3) % 3 != (y % 3 + 3) % 3

    // 取余时处理要负数：
    // 方法1：作差取余 (x - y) % mod 当然仅仅可以用来判断0
    // 方法2: 将余数转化为正数处理 (x % mod + mod) % mod
    return 0;
}

参考代码：

#include <iostream>

using namespace std;

const int N = 5e4 + 10;
int n, k, res, p[N], d[N];
// d[x] 永远存的是到父节点的距离，只不过在下一次使用时，父节点变为了根节点，更新了该值为d[x] = d[x] + d[p[x]];

// 根据题意：四个动物 1->2->3->4 则1 4 为同类 （即 1 2 3, 2 3 4都是一个食物链）
// （都进行模3取余操作）
// 距离为d + 1的点吃距离为d的点
// 与根节点距离相同：为同类
// 与根节点距离差一：为 x -> y
// 与根节点距离差二：为 y -> x

// 只要在一棵树上，就可以根据距离根节点的距离推出二者关系
// 使用并查集维护一个到根节点的距离即可！

int find(int x){
    if(p[x] != x){
        int t = find(p[x]);
        // 路径压缩：d[x]会从根到x一步步累加
        d[x] += d[p[x]];
        p[x] = t;
    }
    return p[x];
}

int main(){
    cin >> n >> k;
    for(int i = 1; i <= n; i++) p[i] = i;
    while(k--){
        int t, x, y;
        cin >> t >> x >> y;
        if(x > n || y > n) res ++;
        else {
            int px = find(x), py = find(y);
            if(t == 1){
                // 负数取余处理：看应用的文件中的"负数取余处理.cpp"
                // px == py 说明已经处理过一次该动物
                if(px == py && (d[x] - d[y]) % 3) res ++;
                else if(px != py) {
                    p[px] = py;
                    // d[x] + d[px] 与 d[y] 模3同余：(d[x] + d[px] - d[y]) % 3 = 0
                    // d[px] = d[y] - d[x] + 3k (k 为任意整数，这里取0即可)
                    d[px] = d[y] - d[x];
                    // 不需要更新d[x]，d[x]由下次find时自动进行路径压缩形式的更新
                }
            }else {
                // (d[y] + 1) % 3 == d[x] % 3
                if(px == py && (d[x] - d[y] - 1) % 3) res ++;
                else if(px != py) {
                    p[px] = py;
                    // (d[x] + d[px]) % 3 = (d[y] + 1) % 3
                    d[px] = d[y] - d[x] + 1;
                }
            }
        }
    }
    cout << res << endl;
    return 0;
}