如何正确实现不相交集数据结构以在Python中查找跨林? [英] How to properly implement disjoint set data structure for finding spanning forests in Python?

问题描述

最近，我正尝试实施google kickstater的2019年编程问题的解决方案，并尝试按照分析说明实施Round E的Cherries Mesh.这是问题和分析的链接. https://codingcompetitions.withgoogle.com/kickstart/round/0000000000050edb/0000000000170721

Recently, I was trying to implement the solutions of google kickstater's 2019 programming questions and tried to implement Round E's Cherries Mesh by following the analysis explanation. Here is the link to the question and the analysis. 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='')

这会通过示例案例，但不会通过测试案例.据我所知，这应该是正确的.我在做错什么吗?

This passes the sample case but not the test cases. To the best of my knowledge, this should be right. Am I doing something wrong?

推荐答案

两个问题:

• 您的算法(用于检查边是否链接两个不相交集，如果不相交则将其联接)效率不高.不相交集数据结构上的联合查找算法效率更高
>
• 最终计数不取决于黑色边缘的原始数量，因为这些黑色边缘可能具有循环，因此不应计算其中的一些.取而代之的是计算总共有多少条边(与颜色无关).由于解决方案代表最小生成树，因此边的数量为 n-1 .减去您拥有的不相交集的数量(就像您已经做过的那样).

• Your algorithm to check whether an edge links two disjoint sets, and join them if not, is inefficient. The Union-Find algorithm on a Disjoint-Set data structure is more efficient
• The final count is not dependent on the original number of black edges, as those black edges may have cycles, and so some of them should not be counted. Instead count how many edges there are in total (irrespective of colour). As the solution represents a minimum spanning tree, the number of edges is n-1. Subtract from that the number of disjoint sets you have (like you already did).

我也建议使用有意义的变量名.该代码更容易理解.单字母变量(例如 t ， q 或 s )不是很有帮助.

I would also advise to use meaningful variable names. The code is much easier to understand. One-letter variables, like t, q or s, are not very helpful.

有几种方法可以实现联合查找"功能.在这里，我定义了一个具有这些方法的 Node 类:

There are several ways to implement the Union-Find functions. Here I have defined a Node class which has those methods:

# Implementation of Union-Find (Disjoint Set)
class Node:
    def __init__(self):
        self.parent = self
        self.rank = 0

    def find(self):
        if self.parent.parent != self.parent:
            self.parent = self.parent.find()
        return self.parent

    def union(self, other):
        node = self.find()
        other = other.find()
        if node == other:
            return True # was already in same set
        if node.rank > other.rank:
            node, other = other, node
        node.parent = other
        other.rank = max(other.rank, node.rank + 1)
        return False # was not in same set, but now is

testcount = int(input())
for testid in range(1, testcount + 1):
    nodecount, blackcount = map(int, input().split())
    # use Union-Find data structure
    nodes = [Node() for _ in range(nodecount)]
    blackedges = []
    for _ in range(blackcount):
        start, end = map(int, input().split())
        blackedges.append((nodes[start - 1], nodes[end - 1]))

    # Start with assumption that all edges on MST are red:
    sugarcount = nodecount * 2 - 2
    for start, end in blackedges:
        if not start.union(end): # When edge connects two disjoint sets:
            sugarcount -= 1 # Use this black edge instead of red one

    print('Case #{}: {}'.format(testid, sugarcount))

这篇关于如何正确实现不相交集数据结构以在Python中查找跨林?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！