并查集是一种松散的数据结构，在求连通问题时很好用．

题目：P3367 【模板】并查集

题目描述#

如题，现在有一个并查集，你需要完成合并和查询操作．

输入格式#

第一行包含两个整数 $N,M$ ,表示共有 $N$ 个元素和 $M$ 个操作．

接下来 $M$ 行，每行包含三个整数 $Z_i,X_i,Y_i$ ．

当 $Z_i=1$ 时，将 $X_i$ 与 $Y_i$ 所在的集合合并．

当 $Z_i=2$ 时，输出 $X_i$ 与 $Y_i$ 是否在同一集合内，是的输出

Y ；否则输出 N ．

输出格式#

对于每一个 $Z_i=2$ 的操作，都有一行输出，每行包含一个大写字母，为 Y 或者 N ．

数据范围#

对于 $100\%$ 的数据， $1\le N\le 2\times 10^5$ ， $1\le M\le 10^6$ ， $1 \le X_i, Y_i \le N$ ， $Z_i \in \{ 1, 2 \}$ ．

思路#

首先，我们假定每一个集合都有一个节点作为代表，我们称那个节点是集合内其余节点的为领导节点．

我们定义一个数组 $f$ ，其中， $f[i]$ 表示的意义为：若 $f[i] = i$ ，即节点 $i$ 是一个领导节点，则 $f[i]$ 表示节点 $i$ 的领导节点．若 $f[i] \neq i$ ，则节点 $i$ 的领导节点就是节点 $f[i]$ 的领导节点．

我们可以使用递归来求一个节点 $a$ 的领导节点，在求的同时，我们可以将求到的值保存到 $f[a]$ 中，下次只需要使用 $O(1)$ 的复杂度就可以求解了，这个行为叫做路径压缩．

// 查找节点i的领导节点，并进行路径压缩
int find(int t)
{
	if (f[t] != t)
		f[t] = find(f[t]);
	return f[t];
}

cpp

我们很容易就可以想到，对于两个节点 $a$ 和 $b$ ，如果想要合并，则可以让 $f[b]$ 设定为 $a$ 的领导节点．如果想要判断是否在同一集合中，只需要判断节点 $a$ 和 $b$ 的领导节点是否相同即可．

// 查询两个节点是否属于同一节点
bool query(int a, int b)
{
	// 查询两个节点的领导节点是否一致
	return find(a) == find(b);
}
// 合并两个节点
void merge(int a, int b)
{
	int x = find(a), y = find(b);
	if (x != y)
		f[x] = y;
}

cpp

最后，千万不要忘了初始化，在最开始，所有节点的领导节点都是它自己．

// 初始化，一开始所有节点的领导节点都是它自己
void init()
{
	for (int i = 1; i <= n; i++)
		f[i] = i;
}

cpp

复杂度分析#

首先，find 函数的复杂度看似好像是最坏 $O(n)$ 的，但是由于有了路径压缩，每一次的 find 都会大大减少下一次 find 相同节点的时间，最终无限趋近于 $O(1)$ ，但常常带有较大的常数．

因此，查询和合并的复杂度也是 $O(1)$ ，综合一下， $m$ 次操作的总复杂度约为 $O(m\log n)$ ．

标程#

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 6;
int n, m;

// 定义一个并查集
class DSU
{
private:
	// f[i]表示第i个节点的领导节点
	int f[N];
	// 查找节点i的领导节点，并进行路径压缩
	int find(int t)
	{
		if (f[t] != t)
			f[t] = find(f[t]);
		return f[t];
	}

public:
	DSU()
	{
		this->init();
	}
	// 初始化，一开始所有节点的领导节点都是它自己
	void init()
	{
		for (int i = 1; i <= n; i++)
			f[i] = i;
	}
	// 查询两个节点是否属于同一节点
	bool query(int a, int b)
	{
		// 查询两个节点的领导节点是否一致
		return find(a) == find(b);
	}
	// 合并两个节点
	void merge(int a, int b)
	{
		int x = find(a), y = find(b);
		if (x != y)
			f[x] = y;
	}
} dsu;

int main()
{
	cin >> n >> m;
	dsu.init();
	for (int i = 1; i <= m; i++)
	{
		int z, x, y;
		cin >> z >> x >> y;
		if (z == 1)
		{
			dsu.merge(x, y);
		}
		else
		{
			cout << (dsu.query(x, y) ? "Y" : "N") << endl;
		}
	}
	return 0;
}

cpp