当前位置：首页 > news >正文

常见算法题型之并查集。附模板题+两道真题

news 2026/8/6 19:02:45

并查集讲解，附模板题，两道真题（PTA，蓝桥杯）

并查集是一种专门处理不相交集合的动态合并与查询问题的数据结构，核心解决「两个元素是否属于同一集合」「合并两个集合」「统计连通分量数量」等连通性问题。优化后单次操作均摊时间复杂度接近 (O(1))，是算法竞赛中最高频的数据结构之一。

一、核心原理

并查集通过父节点数组表示集合关系：每个元素有一个父节点，集合的代表元是树的根节点（父节点指向自身），只要两个元素的根节点相同，就说明它们属于同一个集合。

它只包含两个核心操作：

查找（Find）：找到元素所属集合的根节点
合并（Union）：将两个不相交的集合合并为一个

二、基础实现

1. 初始化

初始状态下每个元素独立成一个集合，父节点指向自己。

constintN=1e5+10;intp[N];// 父节点数组// 初始化：编号从1到nfor(inti=1;i<=n;i++)p[i]=i;

2. 基础查找

递归向上遍历父节点，直到找到根节点。

intfind(intx){if(p[x]!=x)returnfind(p[x]);returnp[x];}

3. 基础合并

找到两个元素的根节点，若根不同则将一棵树挂到另一棵树上。

voidunite(inta,intb){intfa=find(a),fb=find(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是否在同一集合中

解题思路

并查集纯模板题，直接实现带路径压缩的并查集，按指令执行对应操作即可。

完整代码

#include<iostream>usingnamespacestd;constintN=1e5+9;intn,m,p[N];intfind(intx){if(p[x]!=x)p[x]=find(p[x]);returnp[x];}intmain(){cin>>n>>m;for(inti=1;i<=n;i++)p[i]=i;while(m--){charop;inta,b;cin>>op>>a>>b;if(op=='M'){p[find(a)]=find(b);}else{cout<<(find(a)==find(b)?"Yes\n":"No\n");}}return0;}

五、真题实战1：部落问题（PTA L2-024）

https://pintia.cn/problem-sets/994805046380707840/exam/problems/type/7

题目描述

社区中有多个小圈子，朋友的朋友属于同一个部落。统计互不相交的部落总数，以及查询任意两人是否同属一个部落。

解题思路

同一个小圈子的人属于同一部落，将圈子内所有元素合并到同一集合
用set统计所有出现过的编号，得到总人数
统计所有出现过的人的根节点数量，即为部落总数
查询时直接判断两人根节点是否相同

完整代码

#include<bits/stdc++.h>usingnamespacestd;constintN=1e4+9;intp[N];set<int>people;// 记录所有出现过的人intfind(intx){if(p[x]!=x)p[x]=find(p[x]);returnp[x];}intmain(){intn;cin>>n;for(inti=1;i<N;i++)p[i]=i;for(inti=0;i<n;i++){intk,first;cin>>k>>first;people.insert(first);introot=find(first);for(intj=1;j<k;j++){inty;cin>>y;people.insert(y);p[find(y)]=root;}}// 统计部落数量set<int>tribes;for(autox:people)tribes.insert(find(x));cout<<people.size()<<' '<<tribes.size()<<'\n';intq;cin>>q;while(q--){inta,b;cin>>a>>b;cout<<(find(a)==find(b)?"Y\n":"N\n");}return0;}

六、真题实战2：P16237 [蓝桥杯 2026 省 B] 应急布线

[P16237 蓝桥杯 2026 省 B] 应急布线 - 洛谷

题目描述

N NN台计算机通过M MM条残存网线连接，分裂为多个连通区域。添加最少的应急跳线让全网连通，且在跳线总数最少的前提下，让单台计算机接入的跳线数量的最大值尽可能小。
输出最少跳线数、单台最大跳线数的最小值。

解题思路

第一问：最少跳线数

经典结论：k kk个连通块连成整体，最少需要k − 1 k-1k−1条跳线。用并查集统计连通块总数cnt，答案即为cnt-1。

第二问：单台最大跳线数的最小值

分类讨论：

cnt == 1：无需跳线，答案为 0
cnt == 2：只需 1 条跳线，最大值为 1
cnt >= 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

完整代码

#include<bits/stdc++.h>usingnamespacestd;constintN=1e5+9;intp[N],sz[N];intfind(intx){if(p[x]!=x)p[x]=find(p[x]);returnp[x];}intmain(){intn,m;cin>>n>>m;for(inti=1;i<=n;i++){p[i]=i;sz[i]=1;}while(m--){intu,v;cin>>u>>v;intfu=find(u),fv=find(v);if(fu!=fv){p[fu]=fv;sz[fv]+=sz[fu];}}intcnt=0,c1=0;for(inti=1;i<=n;i++){if(find(i)==i){cnt++;if(sz[i]==1)c1++;}}if(cnt==1){cout<<"0 0";return0;}intans1=cnt-1;cout<<ans1<<' ';if(cnt==2){cout<<1;return0;}intc2=cnt-c1;intc3=n-c1;intc4=c3-2*(c2-1);cout<<(c4>=c1?1:2);return0;}