# 并查集 update on 2023/1/14 $(\%100/\%100)$
> ## Tips：并查集真的真的不难
### 零、并查集的用法
众所周知并查集是一个~~很简单的~~东西
只需要用你的~~亿点点~~观察能力and注意力就so easy
并查集=并+查（合并+查询）
并查集往往用树来存，使用$fa$数组表示每个节点的父节点,初始$fa[i]=i$,合并$x,y$时只需将$x$树的根节点与$y$树的根节点连线即可合并，查询$x$的根节点可以使用$find(x)$函数求得。
查:
```cpp
int fa[];//存储每个节点的父节点
int find(int x){
return fa[x] == x ? x : fa[x] = find(fa[x]);
//fa[x] = find(fa[x])路径压缩
//将所有节点的父节点变成这棵树的根节点
}
```
等等，让我们来感性理解一下
路径压缩:
每个节点find后都会指向这棵树的根节点，使每次find时，节点只需一次即可到达根节点
------------
并:
```cpp
int fa[];
int find(int x){}
//同上“查”
void merge(int x , int y){
int rx = find(x) , ry = find(y);
if(rx == ry) return;
//若根节点相同为同一集合不用合并
fa[ry] = rx;//fa[rx] = ry; 两者选一
//将两棵树的根节点连线
return;
}
```
让我们继续来感性理解一下
合并操作:
------------
在主函数记得初始化:
```cpp
int main(){
for(int i = 1; i <= n; i++) fa[i] = i;
//初始化
......
return 0;
}
```
------------
### 一、朴素并查集（又称普通并查集或并查集）
照抄上述代码即可
[P1551 亲戚](https://www.luogu.com.cn/problem/P1551)
太简单了不想讲解了
代码如下:
```cpp
int n , m , p , fa[];
int find(int x){}
void merge(int x , int y){}
//并查集
int main(){
cin >> n >> m >> p;
for(int i = 1; i <= n; i++) fa[i] = i;//初始化
while(m--){
int u , v;
cin >> u >> v;
//合并u,v
}
while(p--){
int u , v;
cin >> u >> v;
if(/*是亲戚*/) puts("Yes");
else puts("No");
}
return 0;
}
```
------------
### 二、种类并查集
前面说的是朴素并查集（也可以是普通并查集$or$并查集），而有时候数据给的很过分，多种物品有多种关系，有可能是互为敌人$or$互为队友，那就需要使用到我们的种类并查集了，其实它就是多个并查集组成，若$a,b$互为敌人，就将$a$本身和$b$的敌人形态合并即可。
如:[P1525 [NOIP2010 提高组] 关押罪犯](https://www.luogu.com.cn/problem/P1525)有敌人和朋友两种关系，先按照$c$从大到小排序，后面就是种类并查集。代码如下:
```cpp
int n , m , f[];
int find(int x){}
void merge(int x , int y){}
//前面都一样
struct node{
int a , b , c;
}x[];
bool cmp(node x , node y){}//cmp函数我就不给了
int main(){
__________;
//输入+初始化
sort(x + 1 , x + 1 + m , cmp);//排序
for(int i = 1; i <= m; i++){
int a = x[i].a , b = x[i].b , c = x[i].c;
if(find(a) == find(b) || find(a + n) == find(b + n)){
cout << c;
return 0;
}//若为同一监狱直接输出c
merge(a , b + n);
merge(b , a + n);
//合并
}
cout << 0;//不会发生冲突
return 0;
}
```
------------
### 三、带权并查集
带权并查集就是每个节点或都有一个或多个权值需要在合并or查询时维护这些权值即可
如[P1196 [NOI2002] 银河英雄传说](https://www.luogu.com.cn/problem/P1196)可以维护一个$pre$数组，$pre[x]$表示x离根结点的距离，那么$ans=abs(pre[x] - pre[y]) - 1$，但若需要维护$pre$数组就必须有一个$num$数组每次$merge$时$pre[ry] += num[ry]$，$num[x]$表示以x作为根节点的树的节点数量，在$find$和$merge$时就可以加上一个值，从而维护$pre$数组求得$ans$。
具体代码如下:
```cpp
int fa[] , pre[] , num[];
int find(int x){
if(fa[x] == x) return x;
int rx = find(fa[x]);
pre[x] += pre[fa[x]];
return fa[x] = rx;
}
void marge(int x , int y){
int rx = find(x) , ry = find(y);
pre[rx] += num[ry];
num[ry] += num[rx];
fa[rx] = ry;
num[rx] = 0;
return;
}
```
好了，并查集就是以上内容了
## 下期内容——[搜索](https://www.luogu.com.cn/blog/liruixiong0101AKIOI/sou-suo)
本文图片均来自百度搜索