一、前言从一道算法题认识并查集今天我们来看一道经典的图论入门题1971. 寻找图中是否存在路径。题目要求给定一个无向双向图判断从起点source到终点destination是否存在有效路径。数据范围极大顶点和边数最高可达2 × 10 5 2\times10^52×105。对于这类判断两点是否连通、集合分组的问题有两种主流解法搜索算法DFS/ BFS构建邻接表遍历图并查集极简代码专门处理连通性问题效率更高。本文结合这道题从零讲解并查集附带通俗易懂原理Python代码新手也能轻松看懂。二、什么是并查集2.1 核心定义并查集全称Disjoint Set UnionDSU不相交集合是一种专门用于管理元素分组的数据结构。它专注解决两个核心问题合并(Union)将两个元素划分到同一个集合查找(Find)查询某个元素的根节点判断两个元素是否属于同一集合。2.2 通俗比喻把每个集合看作一个家族每个元素是家族成员初始化每个人自成一家自己是自己的族长合并两个家族联姻合并为一个家族共用同一个族长查找找到某人的族长判断两个人是否同族连通。2.3 适用场景并查集不擅长复杂图遍历只专注连通性判断常见场景无向图判断两点是否连通统计图中连通分量的个数社交网络好友圈层划分最小生成树Kruskal 算法。三、并查集三大基础操作并查集底层依托数组实现用fa[]数组存储每个元素的父节点fa[x]表示元素x的父节点。3.1 初始化 Init初始状态下每个元素独立成集合父节点指向自身。falist(range(n))# n个顶点0~n-1各自为父3.2 查找 Find核心路径压缩查找元素的根节点并做路径压缩优化递归过程中把沿途所有节点直接挂载到根节点下减少后续查询耗时让查询复杂度近乎O ( 1 ) O(1)O(1)。deffind(x):iffa[x]x:# 找到根节点父节点等于自身returnx fa[x]find(fa[x])# 路径压缩递归回溯直接绑定根节点returnfa[x]3.3 合并 Union合并两个元素所在的集合先分别找到两个元素的根节点若根节点不同则将一个根节点挂载到另一个根节点下完成合并。defunion(u,v):iffind(u)!find(v):# 不属于同一个集合才合并fa[find(u)]find(v)四、LeetCode 1971 并查集题解拆解4.1 完整AC代码classSolution:defvalidPath(self,n:int,edges:List[List[int]],source:int,destination:int)-bool:falist(range(n))# 查找函数路径压缩deffind(x):iffa[x]x:returnx fa[x]find(fa[x])returnfa[x]# 合并函数defunion(u,v):iffind(u)!find(v):fa[find(u)]find(v)# 遍历所有边合并连通的顶点foru,vinedges:union(u,v)# 起点和终点根节点相同 连通returnTrueiffind(source)find(destination)elseFalse4.2 代码逐行解析数组初始化fa list(range(n))所有顶点初始独立find函数递归实现路径压缩扁平化结构提升查询速度union函数判断两个顶点是否同族不同族则合并遍历边无向图双向边遍历所有边完成顶点合并结果判断对比起点和终点的根节点一致则连通返回True。五、DFS解法对比 amp; 优劣分析5.1 DFS原题代码classSolution:defvalidPath(self,n:int,edges:List[List[int]],source:int,destination:int)-bool:# 构建邻接表e[[]for_inrange(n)]foru,vinedges:e[u].append(v)e[v].append(u)sset()# 记录已访问节点defdfs(source,destination):ifsourcedestination:returnTrues.add(source)forvine[source]:ifvnotins:ifdfs(v,destination):returnTruereturnFalsereturndfs(source,destination)5.2 两种解法对比对比维度并查集DFS深度优先搜索代码复杂度极简无需构建邻接表需手动建邻接表、去重访问时间复杂度近乎 O(1)路径压缩优化O(nm) 遍历节点和边大数据适配性优秀适配 2e5 级数据Python递归深度有限大数据栈溢出适用场景仅判断连通性需要遍历路径、搜索节点重点坑点Python默认递归深度约1000本题数据量极大DFS递归写法会直接栈溢出超时而并查集无递归深度限制稳定性更强。六、通用并查集模板这里给大家整理一份通用Python模板包含路径压缩按秩合并双重优化适配绝大多数算法题ps但其实不使用按秩合并启发式合并也行对复杂度影响不大一般情况下路径压缩就够了。classUnionFind:def__init__(self,size):self.parentlist(range(size))# 父节点数组self.rank[1]*size# 秩树的高度用于按秩合并# 查找路径压缩deffind(self,x):ifself.parent[x]!x:self.parent[x]self.find(self.parent[x])returnself.parent[x]# 合并按秩合并防止树过高defunion(self,x,y):x_rootself.find(x)y_rootself.find(y)ifx_rooty_root:returnFalse# 已连通无需合并# 矮树合并到高树下方ifself.rank[x_root]self.rank[y_root]:self.parent[x_root]y_rootelse:self.parent[y_root]x_rootifself.rank[x_root]self.rank[y_root]:self.rank[x_root]1returnTrue七、总结核心本质并查集是处理连通性、集合分组的轻量化数据结构两大优化路径压缩扁平化树、按秩合并限制树高度均摊复杂度近乎常数刷题取舍只判断连通性优先用并查集需要遍历路径、搜索节点再用DFS/BFS本题结论1971题目最优解为并查集代码简洁、不易超时、空间开销小。后续遇到无向图连通、朋友圈、岛屿数量等题目直接套用并查集模板即可快速AC。