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

顾名思义，并查集支持两种操作：

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

以下是并查集的几个例题

一、板子题1

题目概述

给定 $n$ 名学生（编号 $0 \sim n-1$）和 $m$ 个学生团体，每个团体包含若干学生，一个学生可以属于多个团体。

规定：如果某个团体中出现一名嫌疑人，则该团体的所有成员都会变成嫌疑人，并且这种关系会不断传递。

已知学生 $0$ 初始为嫌疑人，求最终所有可能被判定为嫌疑人的学生总数。

思路分析

首先遍历m个学生群体，将一个学生群体中的非同根节点的数加入同一个树。然后遍历一遍和0同一个根节点的数计数。

参考代码

#include<bits/stdc++.h>

using namespace std;

vector<int> s;
int n, m;
void init()
{
	for(int i = 0 ; i < n; i++)
	{
		s[i] = i;
	}
}
int find(int x)
{
	return (x == s[x]) ? x : (s[x] = find(s[x])); //路径压缩 
}
void unite(int x, int y)
{
	int fx = find(x), fy = find(y);
	if(fx != fy)
	{
		s[fy] = fx;
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin >> n >> m;
	s.resize(n);
	init();
	
	for(int i = 0; i < m; i++)
	{
		int k, x;
		cin >> k >> x;
		for(int j = 0; j < k - 1; j++)
		{
			int y;
			cin >> y;
			unite(x,y);
		}
	}
	int cnt = 0;
	for(int i = 0; i < n; i++)
	{
		if(find(i) == find(0)) cnt++;
	}
	cout << cnt;
}

二、板子题2

题目概述

给定 $N$ 个元素（编号为 $1 \sim N$），初始时每个元素各自属于一个独立集合。

共有 $M$ 次操作，每次操作由三个整数 $Z_i, X_i, Y_i$表示：

• 当 $Z_i = 1$ 时，将 $X_i$ 与 $Y_i$ 所在的集合合并；
• 当 $Z_i = 2$ 时，查询 $X_i$​ 与 $Y_i$是否属于同一集合。若是，输出 $\mathrm{Y}$；否则输出 $\mathrm{N}$。

要求依次处理所有操作，并对每个查询操作输出结果。

思路分析

并查集的简单操作

参考代码

#include<bits/stdc++.h>

using namespace std;

int n, m;
vector<int> s;
void init()
{
	for(int i = 1; i <= n; i++)
	{
		s[i] = i;
	}
}
int find(int x)
{
	return (x == s[x]) ? x : (s[x] = find(s[x]));
 } 

void uni(int x, int y)
{
	x = find(x), y = find(y);
	if(x != y)
	{
		s[y] = x;
	}
	return ;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin >> n >> m;
	s.resize(n+1);
	init();
	
	while(m--)
	{
		int z, x, y;
		cin >> z >> x >> y;
		if(z == 1)
		{
			uni(x,y);
		}
		else{
			if(find(x) == find(y))
			{
				cout << "Y" << endl;
				continue;
			 } 
			
			cout << "N" << endl;
			
		}
	}
}

三、奶酪

题目概述

给定一块高度为 $h$ 的奶酪（横向无限大），内部存在 $n$ 个半径相同为 $r$ 的球形空洞。每个空洞由其球心的三维坐标 $(x, y, z)$ 表示。

一只老鼠 Jerry 位于奶酪的下表面（z=0），它可以通过这些空洞移动，但必须满足以下规则：

• 如果两个空洞相交或相切，则 Jerry 可以在这两个空洞之间移动；
• 如果某个空洞与下表面相交或相切，则 Jerry 可以从下表面进入该空洞；
• 如果某个空洞与上表面（z=h）相交或相切，则 Jerry 可以从该空洞到达上表面。

问题是：判断 Jerry 是否可以通过这些空洞，从奶酪的下表面到达上表面。

题解

这道题目的数据量是$10^3$，可以通过遍历两遍来判断每一个空洞是否与其他空洞相连，如果相连接就把它加入并查集。然后将出发点和上表层的点的标给记录下来，最后遍历每个出发点和上表层的点是否是同一个根节点来判断是否存在空洞可以让Jerry到上表层。

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
vector<int> s;
long long dis(long long x,long long y,long long z,long long x1,long long y1,long long z1){
    return (x-x1)*(x-x1)+(y-y1)*(y-y1)+(z-z1)*(z-z1);
}
void init(int n)
{
	for(int i = 0; i < n; i++)
	{
		s[i] = i;
	}
}
int find(int x)
{
	return (x == s[x]) ? s[x] : (s[x] = find(s[x]));
}
void unite(int x,int y)
{
	int fx = find(x), fy = find(y);
	if(fx != fy) s[fy] = fx;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int t;
	cin >> t;
	while(t--)
	{
		ll n, h, r;
		cin >> n >> h >> r;
		int mp[1000],smp[1000];
		vector<tuple<ll,ll,ll>> disk;
		s.resize(n);
		init(n);
		for(int i = 0; i < n; i++)
		{
			ll x, y, z;
			cin >> x >> y >> z;
			disk.emplace_back(x,y,z);
		}
		int index1 = 0, index2 = 0;
		for(int i = 0; i < n; i++)
		{
			ll x = get<0>(disk[i]), y = get<1>(disk[i]), z = get<2>(disk[i]);
			if(llabs(h-z) <= r) mp[index1++] = i;
			if(z <= r) smp[index2++] = i;
		}
		for(int i = 0 ; i < n; i++)
		{
			ll x1 = get<0>(disk[i]), y1 = get<1>(disk[i]), z1 = get<2>(disk[i]);
			for(int j = 0; j <= i; j++)
			{
				ll x2 = get<0>(disk[j]), y2 = get<1>(disk[j]), z2 = get<2>(disk[j]);
				if(((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2)) > 4*r*r) continue;
				if(dis(x1,y1,z1,x2,y2,z2) <= 4*r*r)
				{
					unite(i,j);
				}
			}
		}
		int flag = 0;
		for(int i = 0; i < index1; i++)
		{
			for(int j = 0; j < index2; j++)
			{
				if(find(mp[i]) == find(smp[j]))
				{
					flag = 1;
					break;
				}
				
			}
			if(flag == 1) break;
		}
		if(flag == 1) cout << "Yes" << endl;
		else cout << "No" << endl;
	}
}