本文共 1631 字，大约阅读时间需要 5 分钟。

AC代码解析与实现

1. finder函数

int find(int x) {
    if (x != p[x]) {
        int t = find(p[x]);
        d[x] += d[p[x]];
        p[x] = t;
    }
    return p[x];
}

这个函数主要是路径压缩的实现，通过递归找到集合中的根，同时把当前节点的数据值与路径上的节点的数据值相加，并将路径上的节点直接指向根节点，实际上完成了路径压缩操作。

2. main函数

#include 
   
    
#include 
    
     
#include 
     
      
using namespace std;
const int N = 100010;
int d[N], p[N];
int find(int x) {
    if (x != p[x]) {
        int t = find(p[x]);
        d[x] += d[p[x]];
        p[x] = t;
    }
    return p[x];
}
int main() {
    int res = 0;
    int m, n;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        p[i] = i;
    
    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        
        int px = find(b), py = find(c);
        if (b > n || c > n) {
            res++;
        } else if (a == 1) {
            if (px == py && (d[c] - d[b]) % 3 == 0) {
                res++;
            } else if (px != py) {
                p[px] = py;
                d[px] = d[c] - d[b];
            }
        } else {
            if (b == c) {
                res++;
            } else if (px == py && (d[c] - d[b] - 1) % 3 == 0) {
                res++;
            } else if (px != py) {
                p[px] = py;
                d[px] = d[c] - d[b] - 1;
            }
        }
    }
    printf("%d\n", res);
    return 0;
}
     
    
   

AC代码解释

该代码通过路径压缩和按秩合并实现了并查集算法，效率较高，排序数可以达到近乎线性的时间复杂度。