并查集

构造一个并查集QuickFind的时候,需要指定并查集的容量nn。 并查集的索引从00开始,最大为n1n-1

使用不同的算法,并查集各个操作的时间复杂度有所差异:

并查集类型 connected(p, q) union(p, q)
tango.type.QuickFind(N) O(1)\text{O}(1) O(N)\text{O}(N)
tango.type.WeightedQuickFind(N) O(lnN)\text{O}(\ln N) O(lnN)\text{O}(\ln N)

connected(p, q): boolean

返回一个布尔值,如果两个节点ppqq相互关联,则返回true,否则返回false

count(): number

获得并查集当前的联通组件的数量。

union(p, q): number

将两个节点ppqq相互关联,并返回关联之后的联通组件数。

results matching ""

    No results matching ""