本文主要介绍并集查找，而并集查找同时支持并集和查找操作，其中并集的意思是将两个不相交的集合合并为一个集合，而查询（查找)表示查询两个元素是否在同一个集合中。1、并查示意图的特点是子节点指针指向父亲：2、并查（UnionFind）合并如下图所示，假设并查中的每个元素都做不属于其他集合。下面给出初始指向图：Tips：判断两个元素是否连通，可以通过判断两个元素对应的根节点元素的值是否相等来判断。如果相等，则判断这两个元素属于同一个集合。3.UnionFind简单代码示例3.1PHP代码定义下面是一个UnionFind类，__construct构造函数初始化数据，如果传入size=20，那么$parent会初始化0~19指向自己的节点元素：size=$size;对于($i=0;$i<$size;$i++){$this->parent[$i]=$i;$this->sz[$i]=1;}}/***返回并检查大小*@paramint$p*@paramint$q*@returnint*/publicfunctiongetSize(int$p,int$q):int{return$this->size;}/***找到p对应的集合号*@paramint$p*/publicfunctionfindRoot(int$p){if($p<0||$p>=$this->size){echo"404";出口;}while($p!=$this->parent[$p]){$p=$this->parent[$p];}返回$p;}/***判断两个元素是否属于同一个集合*@paramint$p*@paramint$q*@returnbool*/publicfunctionisConnected(int$p,int$q):bool{return$this->findRoot($p)==$this->findRoot($q);}/***合并两个元素*@paramint$p*@paramint$q*/publicfunctionunionElements(int$p,int$q):void{$pRoot=$this->findRoot($p);$qRoot=$this->findRoot($q);if($pRoot!=$qRoot){if($this->sz[$pRoot]<$this->sz[$qRoot]){//比较两个合并元素的根节点中的元素个数$this->parent[$pRoot]=$qRoot;$this->sz[$qRoot]+=$this->sz[$pRoot];}else{$this->parent[$qRoot]=$pRoot;$this->sz[$pRoot]+=$this->sz[$qRoot];}}}}Tips：代码中的合并方式是根据根节点元素包含的元素总数来确定合并方式的。元素较少的根节点将被合并到元素较多的节点中。也可以根据联合搜索的深度来判断谁被合并了3.2输出演示unionElements($a,$b);}var_dump($uf->isConnected(50,100));//判断50和100是否连通$size=10000;$uf=newUnionFind($size);$m=11000;for($i=0;$i<$m;$i++){$a=mt_rand(0,$大小-1);$b=mt_rand(0,$size-1);$uf->unionElements($a,$b);}var_dump($uf->isConnected(50,100));//判断50和100是否连通，输出如下：代码仓库：https://gitee.com/love-for-po...扫码关注爱因世贤
