目录

• 总目录

1. 并查集
2. 初始化
3. 查询
4. 合并
5. 参考实现

并查集

并查集 是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素．

并查集 支持两种操作：

• 合并（ Unite ）：合并两个元素所属集合（合并对应的树）；
• 查询（ Find ）：查询某个元素所属集合（查询对应的树的根节点），这可以用于判断两个元素是否属于同一集合．

Warning

并查集 某些时候无法以较低复杂度实现集合的分离．

初始化

初始时，每个元素都位于一个单独的集合，表示为一棵只有根节点的树．方便起见，我们将根节点的父亲设为自己．

实现

int f[MAXN]

void IINT () {
  for (int i = 1; i <= MAXN; i++){
    f[i] = i;
  }
  return ;
}

查询

我们需要沿着树向上移动，直至找到根节点．

实现

int find (int fx) {
	if (f[fx] == fx) return fx;
	return find(f[fx]);
}

路径压缩

查询 过程中经过的每个元素都属于该集合，我们可以将其直接连到根节点以加快后续查询．

int find (int fx) {
	if (f[fx] == fx) return fx;
	return f[fx] = find(f[fx]); // 路径压缩
}

合并

要合并两棵树，我们只需要将一棵树的根节点连到另一棵树的根节点．

实现

void unite (int ux, int uy) {
	f[find(ux)] = find(uy);
	return ;
}

参考实现

模板题参考实现

洛谷 P3367 【模板】并查集

#include <bits/stdc++.h>
using namespace std;

int n,m,z,x,y,f[200005];

int find (int fx) {
	if(f[fx] == fx) return fx;
	return f[fx] = find(f[fx]);
}
bool check () {
	return find(x) == find(y);
}
void unite () {
	if(!check()) {
		f[find(x)] = find(y);
	}
	return ;
}

int main () {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		f[i] = i;
	}
	for (int i = 1; i <= m; i++) {
		cin >> z >> x >> y;
		if (z == 1) unite();
		else if(z == 2) {
			if (check()) cout << "Y" << endl;
			else cout << "N" << endl;
		}
	}
	return 0;
}