P3367 并查集
对应章节：序言 → 建议的自学顺序与练习；五、数据结构与算法 → （十四） 并查集。
（一） 任务与输出目标
处理集合合并和同集合查询。
（二） 建模与推导
关系会传递，因此不能只检查两人之间是否直接出现过一条边。每组用一个代表节点，合并时把两组的代表连接；查询时沿 parent 找到最终代表。沿途节点在找到根后直接指向根，后续查询会更短。按组大小把较小树挂到较大树，不必重写组内所有成员。
（三） 手算与过程
先合并 1、2，再合并 2、3，1 与 3 虽未直接连接也具有同一代表；4 仍是另一组。
（四） 带注释实现
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
struct DSU {
vector<int> parent, size;
DSU(int n) : parent(n + 1), size(n + 1, 1) {
iota(parent.begin(), parent.end(), 0);
}
int find(int x) {
return parent[x] == x ? x : parent[x] = find(parent[x]);
} // 路径压缩到代表节点。
bool unite(int a, int b) {
a = find(a);
b = find(b);
if (a == b)
return false;
if (size[a] < size[b])
swap(a, b);
parent[b] = a;
size[a] += size[b];
return true; // 小树挂到大树，控制路径长度。
}
};
void solve() {
int n, m;
cin >> n >> m;
DSU dsu(n);
while (m--) {
int op, a, b;
cin >> op >> a >> b;
if (op == 1)
dsu.unite(a, b);
else
cout << (dsu.find(a) == dsu.find(b) ? "Y" : "N") << '\n'; // 同代表表示同集合。
}
}
signed main() {
ios::sync_with_stdio(false); // 关闭同步，使用 cin 与 cout 完成输入输出。
cin.tie(0), cout.tie(0);
int T = 1; // 本题读入一组数据。
// cin >> T; // 题目给出测试组数时开启，并在 solve 中处理一组。
while (T--)
solve();
}（五） 复杂度
路径压缩与按大小合并，n 次初始化、M 次操作共 \(O(n+M\alpha(n))\)，空间 \(O(n)\)。