前置知识：树的父亲表示法。

并查集基础

并查集，又称 DSU，是一个可以动态维护若干个不重叠的集合的数据结构。

并查集支持的基本操作有两种：

查询一个元素在哪一个集合里。
合并两个集合。

并查集的思想是将每一个集合存储为一棵有根树，以树根为这棵树的代表。我们可以记录一个 $fa$ 数组，存储每一个节点的父亲节点，在合并集合的时候，查询两个节点的根，把一个节点的根接到另外一个节点的根上，就可以合并集合了。

优化

但是，这棵有根树可能退化成链，单次查询的时间复杂度就会退化成 $O(n)$ 。怎么办呢？因为我们只关心一棵树的根，不关心树的具体形态，所以这两棵树是等价的：

路径压缩

我们可以使用“路径压缩”的思想，在查询一个节点 $x$ 的根时，直接将 $fa_x$ 设为 $root_x$ 。使用路径压缩优化以后，每一次查询的均摊时间复杂度变为 $O(\log n)$ 。

按秩合并

还有一种优化方法，就是“按秩合并”。在每一个节点上多维护一个 $siz$ 数组，表示当前节点子树的大小。当合并两棵树时，将 $siz$ 小的树合并到 $siz$ 大的树上，只增加 $siz$ 小的树的查询代价。使用按秩合并优化以后，每一次查询的均摊时间复杂度也是 $O(\log n)$ 。

同时使用路径压缩优化和按秩合并优化的并查集，每一次查询的均摊时间复杂度可看作一个常数忽略不计，与 $O(1)$ 相近。

一般在使用并查集时，我们只需要使用路径压缩优化就够了。

模板题代码：

#include <iostream>

using namespace std;

int n, m, p, f[10001], u, v;
int getfa(int x){
	if (f[x] == x) return x;
	return f[x] = getfa(f[x]);
}
void merge(int a, int b){
	f[getfa(a)] = getfa(b);
}
bool check(int a, int b){
	return getfa(a) == getfa(b);
}
int main(){
	cin >> n >> m;
	for (int i = 1;i <= n;i ++) f[i] = i;
	for (int i = 1;i <= m;i ++){
		cin >> p >> u >> v;
		if (p == 1) merge(u, v);
		else {
		    if (check(u, v)) cout << "Y\n";
		    else cout << "N\n";
		}
	}
}