并查集路径压缩并查集里的find函数里可以进行路径压缩，是为了更快速的查找一个点的根节点。对于一个集合树来说，它的根节点下面可以依附着许多的节点，因此，我们可以尝试在find的过程中，从底向上，如果此时访问的节点不是根节点的话，那么我们可以把这个节点尽量的往上挪一挪，减少数的层数，这个过程就叫做路径压缩。如下图中，find(4)的过程就可以路径压缩，让数的层数更少。节点4往上寻找根节点时，压缩第一步，树的层数就减少了一层：节点2向上寻找，也不是根节点，那么把元素2指向原来父节点的父节点，操后后树的层数相应减少了一层，同时返回根节点0。find过程代码修改为：//查找过程,查找元素p所对应的集合
并查集路径压缩并查集里的find函数里可以进行路径压缩，是为了更快速的查找一个点的根节点。对于一个集合树来说，它的根节点下面可以依附着许多的节点，因此，我们可以尝试在find的过程中，从底向上，如果此时访问的节点不是根节点的话，那么我们可以把这个节点尽量的往上挪一挪，减少数的层数，这个过程就叫做路径压缩。如下图中，find(4)的过程就可以路径压缩，让数的层数更少。节点4往上寻找根节点时，压缩第一步，树的层数就减少了一层：节点2向上寻找，也不是根节点，那么把元素2指向原来父节点的父节点，操后后树的层数相应减少了一层，同时返回根节点0。find过程代码修改为：//查找过程,查找元素p所对应的集合
并查集rank的优化上一小节介绍了并查集基于size的优化，但是某些场景下，也会存在某些问题，如下图所示，操作union(4,2)。根据上一小节，size的优化，元素少的集合根节点指向元素多的根节点。操完后，层数变为4，比之前增多了一层，如下图所示：由此可知，依靠集合的size判断指向并不是完全正确的，更准确的是，根据两个集合层数，具体判断根节点的指向，层数少的集合根节点指向层数多的集合根节点，如下图所示，这就是基于rank的优化。我们在并查集的属性中，添加rank数组，rank[i]表示以i为根的集合所表示的树的层数。...privateint[]rank; //rank[i]表示以i为根的
并查集rank的优化上一小节介绍了并查集基于size的优化，但是某些场景下，也会存在某些问题，如下图所示，操作union(4,2)。根据上一小节，size的优化，元素少的集合根节点指向元素多的根节点。操完后，层数变为4，比之前增多了一层，如下图所示：由此可知，依靠集合的size判断指向并不是完全正确的，更准确的是，根据两个集合层数，具体判断根节点的指向，层数少的集合根节点指向层数多的集合根节点，如下图所示，这就是基于rank的优化。我们在并查集的属性中，添加rank数组，rank[i]表示以i为根的集合所表示的树的层数。...privateint[]rank; //rank[i]表示以i为根的
并查集size的优化按照上一小节的思路，我们把如下图所示的并查集，进行union(4,9)操作。合并操作后的结构为：可以发现，这个结构的树的层相对较高，若此时元素数量增多，这样产生的消耗就会相对较大。解决这个问题其实很简单，在进行具体指向操作的时候先进行判断，把元素少的集合根节点指向元素多的根节点，能更高概率的生成一个层数比较低的树。构造并查集的时候需要多一个参数，sz数组，sz[i]表示以i为根的集合中元素个数。//构造函数publicUnionFind3(intcount){ parent=newint[count]; sz=newint[count]; this.count=cou
并查集size的优化按照上一小节的思路，我们把如下图所示的并查集，进行union(4,9)操作。合并操作后的结构为：可以发现，这个结构的树的层相对较高，若此时元素数量增多，这样产生的消耗就会相对较大。解决这个问题其实很简单，在进行具体指向操作的时候先进行判断，把元素少的集合根节点指向元素多的根节点，能更高概率的生成一个层数比较低的树。构造并查集的时候需要多一个参数，sz数组，sz[i]表示以i为根的集合中元素个数。//构造函数publicUnionFind3(intcount){ parent=newint[count]; sz=newint[count]; this.count=cou
并查集快速合并对于一组数据，并查集主要支持两个动作：union(p,q)-将p和q两个元素连接起来。find(p)-查询p元素在哪个集合中。isConnected(p,q)-查看p和q两个元素是否相连接在一起。在上一小节中，我们用id数组的形式表示并查集，实际操作过程中查找的时间复杂度为O(1)，但连接效率并不高。本小节，我们将用另外一种方式实现并查集。把每一个元素，看做是一个节点并且指向自己的父节点，根节点指向自己。如下图所示，节点3指向节点2，代表3和2是连接在一起的，节点2本身是根节点，所以指向自己。同样用数组表示并查集，但是下面一组元素用parent表示当前元素指向的父节点，每个元素指
并查集快速合并对于一组数据，并查集主要支持两个动作：union(p,q)-将p和q两个元素连接起来。find(p)-查询p元素在哪个集合中。isConnected(p,q)-查看p和q两个元素是否相连接在一起。在上一小节中，我们用id数组的形式表示并查集，实际操作过程中查找的时间复杂度为O(1)，但连接效率并不高。本小节，我们将用另外一种方式实现并查集。把每一个元素，看做是一个节点并且指向自己的父节点，根节点指向自己。如下图所示，节点3指向节点2，代表3和2是连接在一起的，节点2本身是根节点，所以指向自己。同样用数组表示并查集，但是下面一组元素用parent表示当前元素指向的父节点，每个元素指
并查集快速查找本小节基于上一小节并查集的结构介绍基础操作，查询和合并和判断是否连接。查询元素所在的集合编号，直接返回id数组值，O(1)的时间复杂度。...privateintfind(intp){ assertp>=0&&pcount; returnid[p];}...合并元素p和元素q所属的集合，合并过程需要遍历一遍所有元素,再将两个元素的所属集合编号合并，这个过程是O(n)复杂度。...publicvoidunionElements(intp,intq){ intpID=find(p); intqID=find(q); if(pID==qID) return; for(
并查集快速查找本小节基于上一小节并查集的结构介绍基础操作，查询和合并和判断是否连接。查询元素所在的集合编号，直接返回id数组值，O(1)的时间复杂度。...privateintfind(intp){ assertp>=0&&pcount; returnid[p];}...合并元素p和元素q所属的集合，合并过程需要遍历一遍所有元素,再将两个元素的所属集合编号合并，这个过程是O(n)复杂度。...publicvoidunionElements(intp,intq){ intpID=find(p); intqID=find(q); if(pID==qID) return; for(
