并查集理論基礎 | 代碼隨想錄

并查集還是比較簡單的，只要搞清楚兩個事情：

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;
}