algorithm - 如何正确实现不相交集数据结构以在Python中查找跨林？

两个问题：

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

我也建议使用有意义的变量名。该代码更容易理解。只有一个字母的变量，喜欢t，q或者s，不是非常有帮助。

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

# 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))