并查集是一种动态维护多个不重复集合

在并查集中，每个集合都有自己的代表元素。

一个树 $ fa $ 记录每一个元素的归属关系（存储所属集合代表元素的下标）。

具体：

初始状态：

即，每个元素都是一个单独的集合

int fa[mxn];
for (int i = 0; i < n; i++) fa[i] = i;Code language: C++ (cpp)

常见操作

Get

查询一个元素属于哪一个集合（通常题目中会问两个元素是否属于同一集合）

int find(int x) {
    if (fa[x] == x) return x;
    return find(fa[x]);
}Code language: C++ (cpp)

（查询某元素所属集合的代表元素）

那么请考虑这样一种情况：

它退化成了一条链！这样时间复杂度就会大大增加！那么假如元素直接指向代表元素，那假如代表元素迁移（见后）了呢？就在find时实时更新呗！

int find(int x) {
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}Code language: C++ (cpp)

仔细观察代码你会发现只添加了 fa[x]= 这几个字。这就是路径压缩

（有点像记忆化搜索？

查询两个元素是否属于同一集合的代码也很简单

bool is_in_one_set(int b, int c){
    return find(b) == find(c);
}Code language: C++ (cpp)

Merge

把两个元素 $ a $、$ b $ 所在的集合合并为一个

随意修改 $ a $、$ b $ 中一个的父元素为另一个的父元素

void merge(int a, int b) {
    int fa_ = find(a);
    int fb = find(b);
    fa[fa_] = fb;
}
Code language: C++ (cpp)