代码随想录|图论|15并查集理论基础

并查集理论基础 | 代码随想录

并查集还是比较简单的，只要搞清楚两个事情：

1. 并查集是干啥的？解决什么类型问题？
2. 并查集模板（背下来）

1、并查集是干啥的

并查集主要是两个功能：

1. 两个元素添加到同一集合。
2. 判断两个元素是否在同一集合

所以就是合并跟查找。

2、并查集模板

模版就是定义4个函数：

1. 初始化
2. 寻根（优化版更快）
3. 判断
4. 合并 

#include <bits/stdc++.h>
using namespace std;int n=1005;
vector<int> father(n,0);    // 根数组// 并查集初始化
void init()
{for(int i=0;i<n;i++){father[i]=i;}
}// 并查集寻根
int find(int u)
{if(u=father[u])return u;elsereturn find(father[u]);
}// 并查集寻根（优化版）
int find(int u)
{if(u==father[u]) return u;else return father[u]=find(father[u]);
}// 判断u和v是否在一个集合里面
bool isSame(int u,int v)
{u=find(u);v=find(v);return u==v;
}// 将两个元素添加到同一个集合里
void join(int u,int v)
{u=find(u);v=find(v);if(u==v) return;    // 如果根相同，则说明在一个集合father[u]=v;
}