并查集

一开始，每个人都自成一派，互不相识。并查集就是用来处理这种“圈子”或“集合”关系的数据结构

两个基本操作

合并merge
查找find

int find(int x)//返回x的祖宗节点+路径压缩+数组更新
{
    if(p[x]==x) return p[x];
    p[x]=find(p[x]);
    //如果有维护数据数组，也在这里更新 
    return p[x];
}

最基本的并查集

836. 合并集合

维护信息的并查集

维护聚合信息（如总和、最值）

相对简单，每个集合的祖先代表对应的值是这个信息
837. 连通块中点的数量
注意点：
记得初始化数据数组
```
for(int i=1;i<=n;i++){
f[i]=i;
sum[i]=1;//这里每个集合初始大小为1，别忘了
}

在合并的时候，除了赋值f，还要赋值sum
记得特判（一开始忘记了，错了）
 ```
 if(op[0]=='C'){
    int y;scanf("%d",&y);
    int fx=find(x);
    int fy=find(y);
    f[fy]=fx;
    if(fx!=fy){//如果已经是一个集合的了，就不用再执行sum加和的操作，不然会出错 
        sum[fx]+=sum[fy]; 
}   

//其他题目
P1111 修复公路
P3958 [NOIP 2017 提高组] 奶酪
P1197 [JSOI2008] 星球大战

维护相对关系信息（如距离、差值）

也称为“带权并查集”，实现更复杂，需要在路径压缩时同步更新数据。
240. 食物链
分析：
1.为什么可以使用并查集解题
我们不知道动物1是A、B还是C
我们只知道它们之间的相对关系（关键！！！）
比如，如果我知道“X和Y是同类”，以及“Y吃Z”，那么我就可以推断出“X也吃Z
2.用距离数组表示相对关系

3.思路！！！！！！！
如果x和y已经在一个集合，说明之前两者的关系已经确定了，那就判断是否和现有的关系矛盾
如果x和y不在一个集合，说明是第一次出现两者的关系，那就进行合并，并对d[fy]进行赋值
4.易错点：
记得取模！！！
保证d[]数组内的值都是模3意义下的值
4.关键思想：
用维护数组的值来维护种类信息
值相同代表是同一类，值的差判断相对关系

#include <bits/stdc++.h>
using namespace std;

const int N = 50007;

int n, k;
int f[N], d[N]; // d[i]: i到根的关系（模3）

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

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) {
        f[i] = i;
        d[i] = 0;
    }

    int ans = 0;

    for (int i = 1; i <= k; i++) {
        int dd, x, y;
        scanf("%d%d%d", &dd, &x, &y);

        // 越界 或 自吃
        if (x > n || y > n || (dd == 2 && x == y)) {
            ans++;
            continue;
        }

        int fx = find(x);
        int fy = find(y);

        if (fx == fy) {
            int rel = (d[y] - d[x] + 3) % 3;
            if ((dd == 1 && rel != 0) || (dd == 2 && rel != 1)) {
                ans++;
            }
        } else {
            f[fy] = fx;
            if (dd == 1)
                d[fy] = (d[x] - d[y] + 3) % 3;
            else
                d[fy] = (d[x] - d[y] + 1 + 3) % 3;
        }
    }

    printf("%d\n", ans);
    return 0;
}

//其他题目
2294 狡猾的商人 等值的差分方程组
1525 关押罪犯
1196 银河英雄传说

对并查集判断所属集合的正确理解

每个点的f[]记录的不一定就是自己集合的代表父亲元素的编号

只有代表元素的f里存的才是自己的编号
因此find函数有个从上找的过程！！！
这个点有一次突然没绕过来

一个对并查集find理解的更严重的错误

对于路径压缩过后的节点，在执行find时候，还是会递归一次的
因为只有根节点是f[x]==x，第二层依旧不是，所以会递归一次
也正是因为此，d[i]一定要初始化为0
一旦初始化为1，那么后面的点就会因find执行次数而改变值
导致不同点之间d[]的相对情况不同了