查并集
1. 找
intfind(intx,intpa[]){if(pa[x]!=x){find(pa[x],pa[])}returnpa[x];}通过递归，溯源到x的父节点。
对于int pa[] = {0,1,1,1}
下标序列int idx[] = {0,1,2,3}
那么序列2，3的父就是1。如果调用find(3,pa),那么就是
从而找到了3的父节点
2. 将两个节点合并
voidunite(intx,inty,intpa[]){intpx=find(x,pa);intpy=find(y,pa);if(px!=py){pa[py]=px;}return;找到下x和y的父节点
将y的父节点改为x的父节点。
3. 初始化父节点
intpa[100];for(inti=1;i<=100;i++){pa[i]=i;}每个数的初始父节点都是她本身
使用场景
核心本质：快速处理集合的合并、查询两个元素是否同属一个集合，适合动态连通性问题。
一、经典基础场景
1. 连通性判断
无向图中两点是否连通
网络节点是否在同一子网、好友是否同圈子
2. 集合合并
- 帮派合并、朋友圈合并、区域合并
3. 找连通块数量
- 岛屿数量（网格连通）、省份数量、图中连通分量数
二、算法竞赛高频场景
1. 最小生成树 Kruskal 算法
按边权从小到大加边，用并查集判断是否形成环，不连通就合并。
2. 二分图判定（带权并查集）
维护节点间关系（敌对/同类），处理食物链、敌人朋友关系。
3. 区间合并
连续区间合并、区间连通性。
4. 离线处理查询
先把所有操作读入，按顺序合并，再回答查询。
三、实际工程场景
1. 社交网络
判断两个人是否间接好友、社群划分
2. 网络路由
节点连通性、故障域划分
3. 图像分割
像素连通区域聚类
4. 并查集+哈希
动态分组、去重、批量合并分组
四、带权并查集（扩展）场景
维护相对关系，不止简单连通：
食物链（A吃B，B吃C，A和C关系）
关系传递：朋友、敌人、相等、不等
向量偏移、距离关系
五、一句话总结适用条件
只要问题满足：
元素可分组
支持合并两个组
支持查询两点是否同组
优先用并查集，时间复杂度接近 O(α(n))，极快。
