python - 如何在Python中正确实现不相交集数据结构来查找跨越森林？

Question

最近在尝试实现google kickstater 2019年编程题的解答，按照分析讲解尝试实现Round E的Cherries Mesh。这是问题和分析的链接。 https://codingcompetitions.withgoogle.com/kickstart/round/0000000000050edb/0000000000170721

这是我实现的代码:

t = int(input())
for k in range(1,t+1):
    n, q = map(int,input().split())
    se = list()
    for _ in range(q):
        a,b = map(int,input().split())
        se.append((a,b))
    l = [{x} for x in range(1,n+1)]
    #print(se)
    for s in se:
        i = 0
        while ({s[0]}.isdisjoint(l[i])):
            i += 1
        j = 0
        while ({s[1]}.isdisjoint(l[j])):
            j += 1
        if i!=j:
            l[i].update(l[j])
            l.pop(j)
        #print(l)
    count = q+2*(len(l)-1)
    print('Case #',k,': ',count,sep='')

这通过了示例案例，但没有通过测试案例。据我所知，这应该是正确的。我做错了什么吗？

Answer 1

您得到的答案不正确，因为您计算的计数不正确。需要 n-1 条边将 n 个节点连接成树，其中 num_clusters-1 必须是红色。

但是如果你解决这个问题，你的程序仍然会非常慢，因为你的不相交集实现。

值得庆幸的是，实际上用任何编程语言在单个数组/列表/向量中实现非常高效的不相交集合数据结构都非常容易。这是一个用 python 编写的很好的例子。我的盒子上有 python 2，所以我的打印和输入语句与你的有点不同:

# Create a disjoint set data structure, with n singletons, numbered 0 to n-1
# This is a simple array where for each item x:
# x > 0 => a set of size x, and x <= 0 => a link to -x

def ds_create(n):
    return [1]*n

# Find the current root set for original singleton index

def ds_find(ds, index):
    val = ds[index]
    if (val > 0):
        return index
    root = ds_find(ds, -val)
    if (val != -root):
        ds[index] = -root # path compression
    return root

# Merge given sets. returns False if they were already merged

def ds_union(ds, a, b):
    aroot = ds_find(ds, a)
    broot = ds_find(ds, b)
    if aroot == broot:
        return False
    # union by size
    if ds[aroot] >= ds[broot]:
        ds[aroot] += ds[broot]
        ds[broot] = -aroot
    else:
        ds[broot] += ds[aroot]
        ds[aroot] = -broot
    return True

# Count root sets

def ds_countRoots(ds):
    return sum(1 for v in ds if v > 0)

#
# CherriesMesh solution
#
numTests = int(raw_input())
for testNum in range(1,numTests+1):
    numNodes, numEdges = map(int,raw_input().split())
    sets = ds_create(numNodes)
    for _ in range(numEdges):
        a,b = map(int,raw_input().split())
        print a,b
        ds_union(sets, a-1, b-1)
    count = numNodes + ds_countRoots(sets) - 2
    print 'Case #{0}: {1}'.format(testNum, count)