并查集

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

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

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

具体：

初始状态：

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

int fa[10009];
for (int i = 0; i < n; i++) fa[i] = i;

常见操作

Get

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

int find(int x) {
	if (fa[x] == x) return x;
	return find(fa[x]);
}

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

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

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

int find(int x) {
	if (fa[x] == x) return x;
	return fa[x] = find(fa[x]);
}

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

（有点像记忆化搜索？

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

bool is_in_one_set(int b, int c){
    return find(b) == find(c);
}

Merge

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

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

void merge(int a, int b) {
	int fa_ = find(a);
	int fb = find(b);
	fa[fa_] = fb;
}