文章目录并查集并查集的原理并查集的实现并查集的初始化查找元素所在的集合判断两个元素是否在同一个集合合并两个元素所在的集合获取并查集中集合的个数并查集的路径压缩元素的编号问题并查集的题目省份的数量等式方程的可满足性并查集并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。并查集通常用森林来表示，森林中的每棵树表示一个集合，树中的结点对应一个元素。说明一下：虽然利用其他数据结构也能完成不相交集合的合并及查询，但在数据量极大的情况下，其耗费的时间和空间也是极大的。并查集的原理并查集的原理以朋友圈为例，现在有10个人（从0开始编号），刚开始这10个人互不认识，所以各自属于一个集合。如下
大家好，我是爱分享的小蓝，欢迎交流指正~ 全文目录🧭👩👩👦并查集-亲戚问题🚀传送锚点 💡思路点拨🍞代码详解 👶🏻并查集-蓝桥幼儿园🚀传送锚点 💡思路点拨🍞代码详解 🌼并查集-合根植物🚀传送锚点 💡思路点拨🍞代码详解 🏰并查集-城邦🚀传送锚点 💡思路点拨🍞代码详解 并查集=合并成一家人+查找最大的爸爸#7行并查集模板defroot(x):#查找x的祖先是谁（查找根节点）ifp[x]!=x:#如果发现x的爸爸不是自己p[x]=root(p[x])#递归找x的爸爸，直到找到最大的爸爸为止returnp[x]#返回祖先（祖先上面没爸爸，自己是根节点）defunion(x
大家好，我是爱分享的小蓝，欢迎交流指正~ 全文目录🧭👩👩👦并查集-亲戚问题🚀传送锚点 💡思路点拨🍞代码详解 👶🏻并查集-蓝桥幼儿园🚀传送锚点 💡思路点拨🍞代码详解 🌼并查集-合根植物🚀传送锚点 💡思路点拨🍞代码详解 🏰并查集-城邦🚀传送锚点 💡思路点拨🍞代码详解 并查集=合并成一家人+查找最大的爸爸#7行并查集模板defroot(x):#查找x的祖先是谁（查找根节点）ifp[x]!=x:#如果发现x的爸爸不是自己p[x]=root(p[x])#递归找x的爸爸，直到找到最大的爸爸为止returnp[x]#返回祖先（祖先上面没爸爸，自己是根节点）defunion(x
🚀🚀🚀并查集一、概述二、实现🚢2.1QuickFind实现🚢2.2QuickUnion实现三、优化🚢3.1基于size的优化🚢3.2基于rank优化⚓3.2.1路径压缩（PathCompression）⚓3.2.2路径分裂（PathSpliting）⚓3.2.3路径减半（PathHalving）一、概述并查集：一种树型数据结构，用于解决一些不相交集合的合并及查询问题。例如：有n个村庄，查询2个村庄之间是否有连接的路，连接2个村庄两大核心：查找(Find):查找元素所在的集合合并(Union):将两个元素所在集合合并为一个集合二、实现并查集有两种常见的实现思路快查（QuickFind）查找（Fi
题目如下：示例1输入6412231346000000输出14示例2输入6412231346000020输出1题目链接题解or思路：首先如果我们理解题意了，这个题是顶级诈骗。因为是无向图，我们需要记录图中环的大小&环中的炸弹数所以我们可以使用带权并查集来维护。设：环的大小为：cnt环icnt_{环i}cnt环i环中的炸弹数为：cnt炸icnt_{炸i}cnt炸i最终炸弹数的和为：sumsumsum我们可以分两种情况:最终所有节点的炸弹数为000那么答案就是∑cnt环i∗cnt环i\sumcnt_{环i}*cnt_{环i}∑cnt环i∗cnt环i因为：在同一个连通块中任意一点能到达任意一点
目录[Daimayuan]T1倒数第n个字符串（C++，进制）输入格式输出格式样例输入样例输出解题思路[Daimayuan]T2排队（C++，并查集）输入格式输出格式样例输入1样例输出1样例输入2样例输出2样例输入3样例输出3数据规模解题思路[Daimayuan]T3素数之欢（C++，BFS）数据规模输入格式输出格式样例输入样例输出说明解题思路[Daimayuan]T4国家铁路（C++，数学，动态规划）题目描述题目输入题目输出样例输入1样例输出1样例输入2样例输出2解题思路[Daimayuan]T5吃糖果（C++，贪心）输入格式输出格式数据范围输入样例输出样例解题思路[Daimayuan]T6
1什么是并查集正如它的名字一样，并查集（Union-Find）就是用来对集合进行合并（Union）与查询（Find）操作的一种数据结构。合并就是将两个不相交的集合合并成一个集合。查询就是查询两个元素是否属于同一集合。2并查集的优越性对于如下图所示的两个集合，如果我们要判断H和A是否在同一个集合中，我们需要遍历A所在的集合，并逐一判断当前节点是否是H节点，直到最后遍历完整个蓝色集合，才能判断出H节点不在这个集合中。同样的，如果我们需要合并两个集合，就需要遍历整个黄色的集合，将里面的节点一个一个加入到蓝色集合中。两者都是O(N)O(N)O(N)的复杂度。但倘若我们在生成集合的时候，就人为地将集合中
1什么是并查集正如它的名字一样，并查集（Union-Find）就是用来对集合进行合并（Union）与查询（Find）操作的一种数据结构。合并就是将两个不相交的集合合并成一个集合。查询就是查询两个元素是否属于同一集合。2并查集的优越性对于如下图所示的两个集合，如果我们要判断H和A是否在同一个集合中，我们需要遍历A所在的集合，并逐一判断当前节点是否是H节点，直到最后遍历完整个蓝色集合，才能判断出H节点不在这个集合中。同样的，如果我们需要合并两个集合，就需要遍历整个黄色的集合，将里面的节点一个一个加入到蓝色集合中。两者都是O(N)O(N)O(N)的复杂度。但倘若我们在生成集合的时候，就人为地将集合中
并查集和哈希表的实现文章目录并查集和哈希表的实现1.并查集的功能2.并查集的基本原理3.并查集的实现哈希表（hash）1.拉链法2.开放寻址法方法流程代码演示3,字符串哈希1.并查集的功能1.将两个集合进行合并2.询问两个元素是否在一个集合里面2.并查集的基本原理基本原理：每一个集合用一棵树来表示，树根的编号就是整个集合的编号，每一个点存储的都是其父节点，p[x]表示的就是x的父节点要考虑的问题有三个问题一：如何判断树根if(p[x]==x)问题二：如何求x的集合编号while(p[x]!=x)x=p[x]问题三：如何合并两个结合p[x]是x的集合编号，p[y]是y的集合编号,p[x]=y;表
并查集和哈希表的实现文章目录并查集和哈希表的实现1.并查集的功能2.并查集的基本原理3.并查集的实现哈希表（hash）1.拉链法2.开放寻址法方法流程代码演示3,字符串哈希1.并查集的功能1.将两个集合进行合并2.询问两个元素是否在一个集合里面2.并查集的基本原理基本原理：每一个集合用一棵树来表示，树根的编号就是整个集合的编号，每一个点存储的都是其父节点，p[x]表示的就是x的父节点要考虑的问题有三个问题一：如何判断树根if(p[x]==x)问题二：如何求x的集合编号while(p[x]!=x)x=p[x]问题三：如何合并两个结合p[x]是x的集合编号，p[y]是y的集合编号,p[x]=y;表
