一、前言C 语法、面向对象、STL 已经全部收官。从今天开始正式进入高阶数据结构与算法深耕。首篇先学并查集结构简单、代码短、考点极多、适用场景非常广。二、并查集是什么并查集Disjoint Set UnionDSU三个核心操作合并把两个集合合并成一个查找找某个元素的根节点判连通判断两个元素是否在同一个集合形象理解每个人是一个节点认识的人归为一个圈子并查集就是用来管理圈子、合并圈子、查是否同圈。三、并查集核心思想每个节点有一个父节点 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 个元素合并、判断连通输入多组关系统计最终有多少个独立连通块