题目描述

注意两个find的区别

样例

//q3
#include<bits/stdc++.h>
#define N 100010

using namespace std;

int a[N], d[N]; //d为当前节点到父节点到距离

int find(int x){
    if(a[x]!=x){ //注意必须先求dx,再进行更新，确保后续节点更新的时候距离是真实的
        d[x] += d[a[x]]; // 当前节点到父节点 + 父节点到跟节点
        a[x] = find(a[x]);
        return a[x];
    }
    return a[x];
}

int find(int x){
    if(a[x]!=x){ //注意必须先求dx,再进行更新，确保后续节点更新的时候距离是真实的
        int t = a[x];
        a[x] = find(a[x]);
        d[x] += d[t]; // 当前节点到父节点 + 父节点到跟节点
        return a[x];
    }
    return a[x];
}

int main(){
    int n, k, D, x, y;
    int res = 0;
    cin>>n>>k;
    for(int i=0;i<=n;i++) a[i]=i; // 并查集初始化
    while(k--){
        scanf("%d %d %d", &D, &x, &y);
        int fax = find(x), fay = find(y);
        if(x>n || y>n) res++; // x y超出n范围，err
        // else if(D==1 && x == y) res+=1; // 出现x 吃 x情况，err
        else if(D == 1){ // 操作为1时 同类
            //若出现两者是同一集合内的，可以对比， 且 y吃x或者x吃y，即留余为2/1，则为err
            if(fax == fay && ((d[x]-d[y])%3+3)%3 != 0) // +3使得负数变成正数
                res++;
            if(fax != fay){ //只有当两者父节点不一致时「非同一集合，需要转化成同一集合」才需要更新成一致的
                a[fax] = fay;
                d[fax] = d[y] - d[x]; // (d[x]+d[px]-d[y])%3==0 更新到父节点的距离，都是3的倍数，所以fax到父节点的距离与yx之间的距离关系一致
            }
        }
        else{ // 操作为2时
            //若出现两者是在同一集合内，但出现了 同类/y吃x的情况，则为err
            if(fax == fay && ((d[x]-d[y])%3+3)%3 != 1)
                res++;
            if(fax != fay){ //只有当两者父节点不一致时「非同一集合，需要转化成同一集合」才需要更新成一致的
                a[fax] = fay;
                d[fax] = d[y] - d[x] + 1; // (d[x]+d[fax]-d[y]-1)%3==0确保距离为1，即x吃y
            }
        }
    }
    cout<<res<<endl;
    return 0;
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla