并查集的合并

题目:

给2个图G1={V,E1}和G2={V,E2}对应的并查集dsu1[]和dsu2[]

求G={V,E1+E2}的并查集dsu[]

分析:

先初始化一个并查集dsu[i] = i

然后对于每个i,在dsu[]中合并i、getf1(i)和getf2(i)所在集合(合并三个集合)

时间复杂度(O(nalpha(n)))

代码:

原文地址:https://www.cnblogs.com/oier/p/10368183.html