并查集 | OI笔记

并查集

用途：

在近似于 O(1) 的时间内将两个集合合并或询问两个元素是否在一个集合中

基本思想：

每个集合用一棵树表示，用树根编号代表集合。对于每一个子节点都存储它的父节点 p[x]来解决问题

1. 判断两个元素是否属于同一个集合：
   不断查找该节点的父节点 while (p[x] != x) x = p[x] ，直到 p[x] == x为止，即查找到了根节点
2. 合并两个集合：
   只需将 1 集合的根节点连向集合 2 的根节点
   

此时我们发现，对于判断两个元素是否在同一集和的操作，分别需要将两个点遍历到根节点，造成时间复杂度极高

并查集优化 (路径压缩) ：

当遍历一个元素到根节点的过程完成后，将该路径上的每一个点都直接指向根节点，对于下次查找该点以及路径上的其他点，都可以做到 O(1) 查找

代码模板

初始化

int p[N];
// father 数组，用于指向每个节点的父节点
for (int i = 1; i <= n; i ++) p[i] = i;
// 将每个节点的父节点指向自己

查找根节点

int find(int x)
// 返回 x 的根节点，同时处理路径压缩 
{
	if (p[x] != x)
	// 如果 x 不为根节点 
		p[x] = find(p[x]);
		// 向上查找同时将 x 的父节点指向根节点
	
	return p[x];
	// 返回 p[x] 此时的父节点 ( 即为根节点 ) 
}

并查集变种

1. 动态维护每个集合中元素的个数

Acwing837-连通块中点的数量
用集合来维护一个连通块，当在两个数字间连一条边时，即将两个集合合并。

const int N = 1e5 + 10;

int p[N];
int size[N];
// 表示每个集合中点的数量，只保证根节点的 size 有意义 

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

int main()
{
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i ++) 
	{
		p[i] = i;
		size[i] = 1;
	}
	// 将每一个点都建立一个集合
	
	while (m --)
	{
		char op[2];
		int a, b;
		cin >> op;
		if (op[0] == 'C') 
		{
			cin >> a >> b;
			if (find(a) == find(b)) continue;
			size[find(b)] += size[find(a)];
			// 在合并集合的同时，将元素个数同时合并 
			p[find(a)] = find(b);
		}
		else if (op[1] == '1')
		{
			cin >> a >> b;
			if (find(a) == find(b)) cout << "Yes" << endl;
			else cout << "No" << endl;
		}
		else 
		{
			cin >> a;
			cout << size[find(a)] << endl;
		}
	}
}