并查集讲解附模板题两道真题PTA蓝桥杯并查集是一种专门处理不相交集合的动态合并与查询问题的数据结构核心解决「两个元素是否属于同一集合」「合并两个集合」「统计连通分量数量」等连通性问题。优化后单次操作均摊时间复杂度接近 (O(1))是算法竞赛中最高频的数据结构之一。一、核心原理并查集通过父节点数组表示集合关系每个元素有一个父节点集合的代表元是树的根节点父节点指向自身只要两个元素的根节点相同就说明它们属于同一个集合。它只包含两个核心操作查找Find找到元素所属集合的根节点合并Union将两个不相交的集合合并为一个二、基础实现1. 初始化初始状态下每个元素独立成一个集合父节点指向自己。constintN1e510;intp[N];// 父节点数组// 初始化编号从1到nfor(inti1;in;i)p[i]i;2. 基础查找递归向上遍历父节点直到找到根节点。intfind(intx){if(p[x]!x)returnfind(p[x]);returnp[x];}3. 基础合并找到两个元素的根节点若根不同则将一棵树挂到另一棵树上。voidunite(inta,intb){intfafind(a),fbfind(b);if(fa!fb)p[fa]fb;}三、优化策略基础版并查集在极端情况下会退化成链表查找效率骤降。通过优化可以让操作效率接近常数。路径压缩核心思想在查找过程中把路径上所有节点的父节点直接指向根节点让树结构扁平化后续查找可以一步直达根节点。实现只需要修改一行代码intfind(intx){if(p[x]!x)p[x]find(p[x]);// 路径压缩当前节点直接连到根returnp[x];}这是并查集最核心的优化几乎零成本做题时必加。说明仅路径压缩就足以应对绝大多数题目四、模板题AcWing 836. 合并集合836. 合并集合 - AcWing题库题目描述一共有n nn个数编号1 ∼ n 1 \sim n1∼n初始每个数各在一个集合中。共m mm个操作分为两种M a b合并a aa和b bb所在的集合已在同一集合则忽略Q a b询问a aa和b bb是否在同一集合中解题思路并查集纯模板题直接实现带路径压缩的并查集按指令执行对应操作即可。完整代码#includeiostreamusingnamespacestd;constintN1e59;intn,m,p[N];intfind(intx){if(p[x]!x)p[x]find(p[x]);returnp[x];}intmain(){cinnm;for(inti1;in;i)p[i]i;while(m--){charop;inta,b;cinopab;if(opM){p[find(a)]find(b);}else{cout(find(a)find(b)?Yes\n:No\n);}}return0;}五、真题实战1部落问题PTA L2-024https://pintia.cn/problem-sets/994805046380707840/exam/problems/type/7题目描述社区中有多个小圈子朋友的朋友属于同一个部落。统计互不相交的部落总数以及查询任意两人是否同属一个部落。解题思路同一个小圈子的人属于同一部落将圈子内所有元素合并到同一集合用set统计所有出现过的编号得到总人数统计所有出现过的人的根节点数量即为部落总数查询时直接判断两人根节点是否相同完整代码#includebits/stdc.husingnamespacestd;constintN1e49;intp[N];setintpeople;// 记录所有出现过的人intfind(intx){if(p[x]!x)p[x]find(p[x]);returnp[x];}intmain(){intn;cinn;for(inti1;iN;i)p[i]i;for(inti0;in;i){intk,first;cinkfirst;people.insert(first);introotfind(first);for(intj1;jk;j){inty;ciny;people.insert(y);p[find(y)]root;}}// 统计部落数量setinttribes;for(autox:people)tribes.insert(find(x));coutpeople.size() tribes.size()\n;intq;cinq;while(q--){inta,b;cinab;cout(find(a)find(b)?Y\n:N\n);}return0;}六、真题实战2P16237 [蓝桥杯 2026 省 B] 应急布线[P16237 蓝桥杯 2026 省 B] 应急布线 - 洛谷题目描述N NN台计算机通过M MM条残存网线连接分裂为多个连通区域。添加最少的应急跳线让全网连通且在跳线总数最少的前提下让单台计算机接入的跳线数量的最大值尽可能小。输出最少跳线数、单台最大跳线数的最小值。解题思路第一问最少跳线数经典结论k kk个连通块连成整体最少需要k − 1 k-1k−1条跳线。用并查集统计连通块总数cnt答案即为cnt-1。第二问单台最大跳线数的最小值分类讨论cnt 1无需跳线答案为 0cnt 2只需 1 条跳线最大值为 1cnt 3将连通块分为两类孤立点大小为1的连通块数量c1非孤立连通块大小≥2数量c2 cnt - c1总点数c3 n - c1先将非孤立连通块连成链消耗c2-1条跳线占用2 × ( c 2 − 1 ) 2\times(c2-1)2×(c2−1)个接口剩余可用接口c4 c3 - 2*(c2-1)。若c4 c1所有孤立点可直接接在非孤立块上每点仅1条线最大值为1若c4 c1部分孤立点需要串联会出现接2条线的节点最大值为2完整代码#includebits/stdc.husingnamespacestd;constintN1e59;intp[N],sz[N];intfind(intx){if(p[x]!x)p[x]find(p[x]);returnp[x];}intmain(){intn,m;cinnm;for(inti1;in;i){p[i]i;sz[i]1;}while(m--){intu,v;cinuv;intfufind(u),fvfind(v);if(fu!fv){p[fu]fv;sz[fv]sz[fu];}}intcnt0,c10;for(inti1;in;i){if(find(i)i){cnt;if(sz[i]1)c1;}}if(cnt1){cout0 0;return0;}intans1cnt-1;coutans1 ;if(cnt2){cout1;return0;}intc2cnt-c1;intc3n-c1;intc4c3-2*(c2-1);cout(c4c1?1:2);return0;}七、总结并查集是连通性问题的首选数据结构核心要点两个核心操作find找根、union合并路径压缩是必加优化实现简单收益极高常见考法连通块计数、连通性判断、带权并查集扩展域等解题关键将题目抽象为「集合合并连通判断」模型再套用并查集 常见算法题型之并查集。附模板题+两道真题
并查集讲解附模板题两道真题PTA蓝桥杯并查集是一种专门处理不相交集合的动态合并与查询问题的数据结构核心解决「两个元素是否属于同一集合」「合并两个集合」「统计连通分量数量」等连通性问题。优化后单次操作均摊时间复杂度接近 (O(1))是算法竞赛中最高频的数据结构之一。一、核心原理并查集通过父节点数组表示集合关系每个元素有一个父节点集合的代表元是树的根节点父节点指向自身只要两个元素的根节点相同就说明它们属于同一个集合。它只包含两个核心操作查找Find找到元素所属集合的根节点合并Union将两个不相交的集合合并为一个二、基础实现1. 初始化初始状态下每个元素独立成一个集合父节点指向自己。constintN1e510;intp[N];// 父节点数组// 初始化编号从1到nfor(inti1;in;i)p[i]i;2. 基础查找递归向上遍历父节点直到找到根节点。intfind(intx){if(p[x]!x)returnfind(p[x]);returnp[x];}3. 基础合并找到两个元素的根节点若根不同则将一棵树挂到另一棵树上。voidunite(inta,intb){intfafind(a),fbfind(b);if(fa!fb)p[fa]fb;}三、优化策略基础版并查集在极端情况下会退化成链表查找效率骤降。通过优化可以让操作效率接近常数。路径压缩核心思想在查找过程中把路径上所有节点的父节点直接指向根节点让树结构扁平化后续查找可以一步直达根节点。实现只需要修改一行代码intfind(intx){if(p[x]!x)p[x]find(p[x]);// 路径压缩当前节点直接连到根returnp[x];}这是并查集最核心的优化几乎零成本做题时必加。说明仅路径压缩就足以应对绝大多数题目四、模板题AcWing 836. 合并集合836. 合并集合 - AcWing题库题目描述一共有n nn个数编号1 ∼ n 1 \sim n1∼n初始每个数各在一个集合中。共m mm个操作分为两种M a b合并a aa和b bb所在的集合已在同一集合则忽略Q a b询问a aa和b bb是否在同一集合中解题思路并查集纯模板题直接实现带路径压缩的并查集按指令执行对应操作即可。完整代码#includeiostreamusingnamespacestd;constintN1e59;intn,m,p[N];intfind(intx){if(p[x]!x)p[x]find(p[x]);returnp[x];}intmain(){cinnm;for(inti1;in;i)p[i]i;while(m--){charop;inta,b;cinopab;if(opM){p[find(a)]find(b);}else{cout(find(a)find(b)?Yes\n:No\n);}}return0;}五、真题实战1部落问题PTA L2-024https://pintia.cn/problem-sets/994805046380707840/exam/problems/type/7题目描述社区中有多个小圈子朋友的朋友属于同一个部落。统计互不相交的部落总数以及查询任意两人是否同属一个部落。解题思路同一个小圈子的人属于同一部落将圈子内所有元素合并到同一集合用set统计所有出现过的编号得到总人数统计所有出现过的人的根节点数量即为部落总数查询时直接判断两人根节点是否相同完整代码#includebits/stdc.husingnamespacestd;constintN1e49;intp[N];setintpeople;// 记录所有出现过的人intfind(intx){if(p[x]!x)p[x]find(p[x]);returnp[x];}intmain(){intn;cinn;for(inti1;iN;i)p[i]i;for(inti0;in;i){intk,first;cinkfirst;people.insert(first);introotfind(first);for(intj1;jk;j){inty;ciny;people.insert(y);p[find(y)]root;}}// 统计部落数量setinttribes;for(autox:people)tribes.insert(find(x));coutpeople.size() tribes.size()\n;intq;cinq;while(q--){inta,b;cinab;cout(find(a)find(b)?Y\n:N\n);}return0;}六、真题实战2P16237 [蓝桥杯 2026 省 B] 应急布线[P16237 蓝桥杯 2026 省 B] 应急布线 - 洛谷题目描述N NN台计算机通过M MM条残存网线连接分裂为多个连通区域。添加最少的应急跳线让全网连通且在跳线总数最少的前提下让单台计算机接入的跳线数量的最大值尽可能小。输出最少跳线数、单台最大跳线数的最小值。解题思路第一问最少跳线数经典结论k kk个连通块连成整体最少需要k − 1 k-1k−1条跳线。用并查集统计连通块总数cnt答案即为cnt-1。第二问单台最大跳线数的最小值分类讨论cnt 1无需跳线答案为 0cnt 2只需 1 条跳线最大值为 1cnt 3将连通块分为两类孤立点大小为1的连通块数量c1非孤立连通块大小≥2数量c2 cnt - c1总点数c3 n - c1先将非孤立连通块连成链消耗c2-1条跳线占用2 × ( c 2 − 1 ) 2\times(c2-1)2×(c2−1)个接口剩余可用接口c4 c3 - 2*(c2-1)。若c4 c1所有孤立点可直接接在非孤立块上每点仅1条线最大值为1若c4 c1部分孤立点需要串联会出现接2条线的节点最大值为2完整代码#includebits/stdc.husingnamespacestd;constintN1e59;intp[N],sz[N];intfind(intx){if(p[x]!x)p[x]find(p[x]);returnp[x];}intmain(){intn,m;cinnm;for(inti1;in;i){p[i]i;sz[i]1;}while(m--){intu,v;cinuv;intfufind(u),fvfind(v);if(fu!fv){p[fu]fv;sz[fv]sz[fu];}}intcnt0,c10;for(inti1;in;i){if(find(i)i){cnt;if(sz[i]1)c1;}}if(cnt1){cout0 0;return0;}intans1cnt-1;coutans1 ;if(cnt2){cout1;return0;}intc2cnt-c1;intc3n-c1;intc4c3-2*(c2-1);cout(c4c1?1:2);return0;}七、总结并查集是连通性问题的首选数据结构核心要点两个核心操作find找根、union合并路径压缩是必加优化实现简单收益极高常见考法连通块计数、连通性判断、带权并查集扩展域等解题关键将题目抽象为「集合合并连通判断」模型再套用并查集