文章目录一、并查集概述二、并查集算法实现一、并查集概述并查集Union-Find又称不相交集合Disjoint Set Union, DSU是一种用于处理不相交集合的合并与查询问题的数据结构。它支持两种主要操作查找Find确定一个元素属于哪个集合。合并Union将两个不同的集合合并成一个集合。并查集常见的存储方式是使用数组来模拟树结构利用数组存储每个元素的父节点信息。数组的下标对应元素编号数组中存储的值代表该元素的父节点编号。通过不断查找元素的父节点最终找到根节点以此确定元素所属的集合。在学习并查集之前有一些相关的概念需要大家先行理解和掌握具体如下集合在并查集里集合代表一组具有某种关联元素的组合这些元素在逻辑上被视为一个整体。例如在社交网络场景中每个集合可以表示一个朋友圈子圈子里的人通过好友关系相互连接。元素元素是构成集合的基本单位。以社交网络为例每个用户就是一个元素这些元素根据其好友关系被划分到不同的集合中。连通分量连通分量是指在图中相互连通的元素所构成的最大子集。在并查集的应用中一个连通分量对应着一个集合。比如在地图连通性问题里相互可达的地点构成一个连通分量在并查集中就表示为一个集合。查找查找操作是指找出某个元素所属的集合。通常通过不断追溯元素的父节点直到找到根节点根节点代表该元素所在的集合。例如在判断社交网络中两个用户是否属于同一个朋友圈子时就需要对这两个用户进行查找操作若它们的根节点相同则属于同一个朋友圈子。合并合并操作是将两个不同的集合合并成一个集合。当有新的关系建立时就需要进行合并操作。比如在社交网络中当两个原本不认识的用户成为好友时就需要将他们各自所在的朋友圈子合并成一个更大的朋友圈子。二、并查集算法实现代码模板int n 1005; // n根据题目中节点数量而定一般比节点数量大一点就好 vectorint father vectorint (n, 0); // C里的一种数组结构 // 并查集初始化 void init() { for (int i 0; i n; i) { father[i] i; } } // 并查集里寻根的过程 int find(int u) { return u father[u] ? u : father[u] find(father[u]); // 路径压缩 } // 判断 u 和 v是否找到同一个根 bool isSame(int u, int v) { u find(u); v find(v); return u v; } // 将v-u 这条边加入并查集 void join(int u, int v) { u find(u); // 寻找u的根 v find(v); // 寻找v的根 if (u v) return ; // 如果发现根相同则说明在一个集合不用两个节点相连直接返回 father[v] u; }