合并两个集合void UnionUnionFindSet set int x int y int xRoot = Findset x; int yRoot = Findset y; if xRoot == yRoot return; if set-rankxRoot set-rankyRoot set-parentxRoot =
这段代码实现了并查集中的合并操作,即将两个集合合并成一个集合。其中,UnionFindSet是一个结构体,包含两个数组:parent和rank。parent数组用来记录每个元素的父节点,rank数组用来记录每个元素所在集合的树的深度(即树的高度)。
具体实现过程如下:
-
首先通过Find函数找到x和y所在集合的根节点xRoot和yRoot。
-
如果xRoot和yRoot已经相等,说明它们已经在同一个集合中,不需要再进行合并操作,直接返回。
-
如果xRoot所在集合的树比yRoot所在集合的树深度小,则将xRoot的父节点设为yRoot,即将xRoot所在集合合并到yRoot所在集合中。
-
如果yRoot所在集合的树比xRoot所在集合的树深度小,则将yRoot的父节点设为xRoot,即将yRoot所在集合合并到xRoot所在集合中。
-
如果xRoot和yRoot所在集合的树深度相等,则将yRoot的父节点设为xRoot,并将xRoot所在集合的树的深度加1,即将yRoot所在集合合并到xRoot所在集合中,并将xRoot所在集合的树的深度加1。
最终,两个集合被合并成一个集合,其中所有元素都有相同的根节点
原文地址: http://www.cveoy.top/t/topic/gDAh 著作权归作者所有。请勿转载和采集!