C++ 代码 并查集

#include <iostream> //可以一种树状结构来模拟题意，根节点是0，能吃0的为1，能吃1的为2，能吃2的为3，而又因为0也能吃2，所以0与2同类
#include <algorithm>//之后的情况类似，因此3是一个循环(y-x)%3==0,则x,y是同类,(y-x)%3==1即(y-x-1)%3==0，则y吃x，所以可以用离根节点的距离来表示物种间相互关系
using namespace std;//若出现的物种是之前没有的(根据根节点是否相同来判断)，则合并集合，如果有，就根据上述关系判断是否为真
const int N = 1e5 + 10;
int d[N];   //存储各节点到各自根节点距离
int p[N];   //父节点
int find(int x)     //并查集关键步骤，路径压缩+维护距离
{
    int t;
    if(x != p[x]){
        t = find(p[x]); //先记录根节点
        d[x] += d[p[x]];    //在递归回来时求得距离
        p[x] = t;   //返回根节点
    }
    return p[x];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,k;
    int D,x,y;
    int px,py;
    int res = 0;
    cin >> n >> k;
    for(int i = 1; i <= n; ++i)     //初始化，从1到n
        p[i] = i;
    while(k--){
        cin >> D >> x >> y;
        if(x > n || y > n)  //第一个条件
            ++res;
        else{
            px = find(x) , py = find(y);    //寻找各自根节点
            if(D == 1){ //同类
                if(px == py && (d[x] - d[y]) % 3)   //如果它们根节点相等即之前这些节点出现过，并且它们的距离之差模3不为0，说明它们不是同类
                    ++res;
                else if(px != py){  //如果这些是新节点，之前没有添加到集合中
                    p[px] = py; //合并集合,py作为新根节点
                    d[px] = d[y] - d[x];    //更新px到新根节点py距离：(d[x]+d[px]-d[y]) % 3 =0,解得d[px] = d[y] - d[x]，d[x]在之后的find函数中会被更新
                }
            }
            else{   //x吃y，即(x-y) % 3 = 1
                if(px == py && (d[x] - d[y] - 1) % 3)   //与同类的情况同理
                    ++res;
                else if(px != py){
                    p[px] = py;
                    d[px] = d[y] + 1 - d[x];
                }
            }
        }
    }
    cout << res << endl;
    return 0;
}