一、前言
C++ 语法、面向对象、STL 已经全部收官。从今天开始，正式进入高阶数据结构与算法深耕。首篇先学并查集：结构简单、代码短、考点极多、适用场景非常广。
二、并查集是什么
并查集（Disjoint Set Union，DSU）三个核心操作：
- 合并：把两个集合合并成一个
- 查找：找某个元素的根节点
- 判连通：判断两个元素是否在同一个集合
形象理解：每个人是一个节点，认识的人归为一个圈子，并查集就是用来管理圈子、合并圈子、查是否同圈。
三、并查集核心思想
- 每个节点有一个父节点 parent []
- 根节点：自己的父节点是自己
- 找祖先：一路往上找，直到父节点等于自身
- 合并集合：把一个集合的根，挂到另一个集合根下面
四、基础朴素版并查集
1. 初始化
每个人初始自己是一个集合，父节点等于自己
const int N = 1005; int parent[N]; // 初始化 void init(int n) { for(int i = 1; i <= n; i++) { parent[i] = i; } }2. 查找根节点
int find(int x) { if(parent[x] == x) return x; return find(parent[x]); }3. 合并两个集合
void unite(int x, int y) { int fx = find(x); int fy = find(y); if(fx != fy) { parent[fy] = fx; } }4. 判断是否连通
bool isSame(int x, int y) { return find(x) == find(y); }五、优化一：路径压缩（必加）
朴素版查找层数多、效率低。路径压缩：查找时把沿途所有节点直接挂到根节点，下次查找 O (1)。
优化后 find 函数：
int find(int x) { if(parent[x] == x) return x; // 路径压缩：递归回溯直接指向根 parent[x] = find(parent[x]); return parent[x]; }刷题默认必写路径压缩。
六、优化二：按秩合并（可选）
维护树的高度 / 节点数量，合并时小树挂大树，防止树过高。日常刷题只写路径压缩就够用，竞赛再加上按秩合并。
七、并查集完整万能模板（可直接复制刷题）
#include <iostream> using namespace std; const int N = 1005; int parent[N]; // 初始化 void init(int n) { for(int i = 1; i <= n; ++i) parent[i] = i; } // 查找 + 路径压缩 int find(int x) { if(parent[x] != x) parent[x] = find(parent[x]); return parent[x]; } // 合并 void unite(int x, int y) { x = find(x); y = find(y); if(x != y) parent[y] = x; } // 判断同集合 bool same(int x, int y) { return find(x) == find(y); } int main() { int n,m; cin >> n >> m; init(n); while(m--) { int op,x,y; cin >> op >> x >> y; if(op == 1) unite(x,y); else { if(same(x,y)) cout << "Yes\n"; else cout << "No\n"; } } return 0; }八、经典适用场景
- 判断图中两点是否连通
- 朋友圈、亲戚关系合并
- 最小生成树 Kruskal 算法必备
- 岛屿数量、连通块统计
- 区间合并、分组问题
九、今日核心总结
- 并查集三大操作：初始化、查找、合并
- 路径压缩是标配优化，极大提升效率
- 模板固定，刷题直接套用即可
- 常用于连通性判断、集合合并、图论基础题
十、课后练习
- 手写并查集模板，实现 5 个元素合并、判断连通
- 输入多组关系，统计最终有多少个独立连通块
