教科书中Union-Find算法的实现不起作用

Question

我有两个联合查找的实现:一个是我自己提出的(它可以工作)，另一个是基于教科书上的解释(令人惊讶的是，它不工作)。当我在调试错误的实现时，也许有人能够指出一个错误，到目前为止，我还没有意识到这个错误。

我一直在使用以下内容：

https://www.cl.cam.ac.uk/teaching/1415/Algorithms/disjointsets.pdf

有关更多信息，请参阅以下内容：

https://en.wikipedia.org/wiki/Disjoint-set_data_structure

https://cp-algorithms.com/data_structures/disjoint_set_union.html

实现代码：

from collections import Counter

def edges2vertices(edges):
    return sorted(list({vertex for edge in edges for vertex in edge}))

class UnionFindTextbook:
    def __init__(self, vertices):
        self._parents = {vertex: vertex for vertex in vertices}

    def find(self, s):
        if s == self._parents[s]:
            return s
        self._parents[s] = self.find(self._parents[s])
        return self._parents[s]

    def union(self, a, b):
        a = self.find(a)
        b = self.find(b)
        if a != b:
            self._parents[b] = a

    @property
    def partitions(self):
        return Counter(self._parents.values()).values()

class UnionFindOwn:
    def __init__(self, vertices):
        self._lookup = {v: idx for idx, v in enumerate(vertices)}
        self._forest = [[vertex] for vertex in vertices]

    def union(self, a, b):
        a = self.find(a)
        b = self.find(b)
        if self._should_merge(a, b) and self._can_merge(a, b):
            self._forest[a].extend(self._forest[b])
            for i in self._forest[b]:
                self._lookup[i] = a
            self._forest[b] = []

    def find(self, a):
        return self._lookup[a]

    def _should_merge(self, a, b):
        return a != b

    def _can_merge(self, a, b):
        return self._forest[a] and self._forest[b]

    @property
    def partitions(self):
        return [len(tree) for tree in self._forest if tree]

def unionfind_min_max(edges, strategy):
    vertices = edges2vertices(edges)
    uf = strategy(vertices)
    for a, b in edges:
        uf.union(a, b)
    return min(uf.partitions), max(uf.partitions)

测试代码：

import unittest
from typing import List, Tuple

import ddt

from unionfind import unionfind_min_max, UnionFindOwn as STRATEGY

DATA_UNIONFIND_MIN_MAX = [
    {  # 1.
       # 5
       # 3-8
       # 4-9
       # 1-6-2-7
        "edges": [
            (1, 6),
            (2, 7),
            (3, 8),
            (4, 9),
            (2, 6),
        ],
        "strategy": STRATEGY,
        "expected": (2, 4),
    },
]

@ddt.ddt
class TestUnionFind(unittest.TestCase):
    @ddt.unpack
    @ddt.data(*DATA_UNIONFIND_MIN_MAX)
    def test_unionfind_min_max(self, edges: List[Tuple[int]], strategy, expected: Tuple[int]) -> None:
        actual = unionfind_min_max(edges, strategy)
        self.assertEqual(expected, actual)

有人能指出UnionFindTextbook中的错误吗？

最小可重现示例：

from collections import Counter

def edges2vertices(edges):
    return sorted(list({vertex for edge in edges for vertex in edge}))

class UnionFindTextbook:
    def __init__(self, vertices):
        self._parents = {vertex: vertex for vertex in vertices}

    def find(self, s):
        if s == self._parents[s]:
            return s
        self._parents[s] = self.find(self._parents[s])
        return self._parents[s]

    def union(self, a, b):
        a = self.find(a)
        b = self.find(b)
        if a != b:
            self._parents[b] = a

    @property
    def partitions(self):
        return Counter(self._parents.values()).values()

def unionfind_min_max(edges, strategy=UnionFindTextbook):
    vertices = edges2vertices(edges)
    uf = strategy(vertices)
    for a, b in edges:
        uf.union(a, b)
    return min(uf.partitions), max(uf.partitions)

edges = [
    (1, 6),
    (2, 7),
    (3, 8),
    (4, 9),
    (2, 6),
]

assert unionfind_min_max(edges) == (2, 4)

Answer 1

我已经设法适当地修改了代码，但是我不确定为什么所有的源代码都没有提到在union()操作之后数据结构将不会处于所需的状态。

@property
def partitions(self):
    return Counter(self.find(i) for i in self._parents).values()

有什么想法吗？