1.什么是组合检查1.解释维基百科解释的内容？你在说什么？我不明白？再说说人话吧。通俗点说，联合查找是一种数据结构，就是说在一些有N个元素的集合应用问题中，通常在开始的时候，每个元素组成一个单元素集合，然后按照一定的顺序合并其中的集合属于同一组的元素进行定位，期间需要反复查找某个元素在哪个集合中。用于处理一些不相交集合的合并和查询问题。2.有什么优势？经过足够多的合并查询操作后，单次查询的平均时间复杂度为O(1)。3.功能是解决相似图的连通性问题，被广泛使用和搜索。二、主要操作1、初始化：初始化每个点所在的集合。一般来说，每次使用该数据结构时，只需要执行一次该步骤即可。不管采用哪种实现方式，时间复杂度都是O(N)。2、搜索：找到元素所在的集合，即这个集合的代表节点——根节点3、合并：将两个元素所在的集合合并为一个集合。一个小集合连接到一个大集合。一般来说，合并前要判断两个元素是否属于同一个集合，可以通过上面的“查找”操作来实现。三、路径优化和压缩1、思路：每次搜索，如果路径较长，修改信息，这样下次搜索会更快。2.实现：第一步是找到根节点；第二步是修改搜索路径上的所有节点，并将它们指向根节点。为什么最终的摊销时间复杂度为O(1)？路径优化和压缩是关键，因为每次执行搜索时，路径上的所有节点都将直接连接到根节点。后面查找的时候，除了查找根节点，一步就找到了根节点。操作本身是O(1)，一条路径的调整操作只会执行一次，所以最终的摊销时间复杂度是O(1)。时间复杂度O(1)的证明和搜索最早由BernardA.Galler和MichaelJ.Fischer于1964年提出，但直到1989年Fredman和Saks证明任何并集和搜索都需要O(1)的摊销完成每个操作的时间需要25年才能证明完成。4.核心方法/***@authorJava与算法学习：Monday*/publicstaticclassUnionFind{//用户输入的V对应内部NodepublicHashMap>节点；//谁是Node的父亲publicHashMap,Node>parents;//Node所在集合的大小（只有集合的代表节点<可以理解为头节点>才会放在sizeMap中）publicHashMap,Integer>sizeMap;//初始化时将用户给的所有数据放入每个Map中publicUnionFind(Listvalues){nodes=newHashMap<>();parents=newHashMap<>();sizeMap=newHashMap<>();for(Vcurrent:values){Nodenode=newNode<>(current);ent,nodes.put();//初始化时节点的父亲本身就是parents.put(node,node);//节点初始化时的大小为1sizeMap.put(node,1);/***查找指定节点所在的代表节点**@authorJava与算法学习：星期一*/publicNodefindHead(Nodenode){Node当前=节点；堆栈<节点>堆栈=新堆栈<>();//当前节点的父节点不是自己，说明没有找到topwhile(current!=parents.get(current)){stack.push(current);当前=parents.get(当前);}//优化：修改搜索路径上的所有节点，指向根节点while(!stack.isEmpty()){parents.put(stack.pop(),current);}returncurrent;}2.isSameSet(Va,Vb)判断a和b代表的两个集合是否在同一个集合/***判断两个节点所在的集合是否不是同一个集合**@authorJava与算法学习：周一*/publicbooleanisSameSet(Va,Vb){returnfindHead(nodes.get(a))==findHead(nodes.get(b));}3.union(Va,Vb)将a和b代表的两个集合合并为一个集合/***将两个节点所在的集合合并为一个集合**@authorJava与算法学习：星期一*/publicvoidunion(Va,Vb){NodeaHead=findHead(nodes.get(a));节点bHead=findHead(nodes.get(b));if(aHead!=bHead){//说明a和b的集合不是同一个集合intaSize=sizeMap.get(aHead);intbSize=sizeMap.get(bHead);//找到一个更大尺寸的集合Nodebig=aSize>=bSize?a头:b头;节点small=big==aHead?b头：一个头；//小的接大的（这也是一种优化）parents.put(small,big);//重新调整big所在集合的大小sizeMap.put(big,aSize+bSize);//small所在的set已经和big相连，从sizeMap中移除sizeMap.remove(small);}}所有代码地址：https://github.com/monday-pro/algorithm-study/blob/master/src/basic/unionfind/TheUnionFind.java五、省份数1、题目描述LeetCode547https://leetcode-cn.com/probl...有n个城市，有的是相连的，有的是不相连的。如果a市与b市直接相连，b市与c市直接相连，则a市与c市间接相连。省是一组直接或间接连接的城市，不包含其他未连接的城市。给定一个nxn矩阵isConnected，其中isConnected[i][j]=1表示城市i直接连接到城市j，而isConnected[i][j]=0表示它们没有直接连接。返回矩阵中的省份数。2.输入示例：isConnected=[[1,1,0],[1,1,0],[0,0,1]][1,1,0][1,1,0][0,0,1]输出:23.如果你知道如何通过组合和检查来解决问题，那么问题就解决了。一个接一个地使用并检查连接的城市，将它们合并在一起。最后，合并和检查集的数量就是省份的数量。等价于联合查找时可以作为黑盒使用。4.代码为了优化代码的执行时间，将Map最初表示的集合用一维数组表示。/***@authorJava和算法学习：星期一*/publicintfindCircleNum(int[][]isConnected){intlength=isConnected.length;UnionFindunionFind=newUnionFind(长度);//因为整个n*n的二维矩阵是关于对角线对称的，并且自身与自身相连，即对角线全为1，所以我们只需要遍历其中一侧即可。//我们遍历右上角的数据for(inti=0;i
