Source code for titan_pylib.data_structures.union_find.union_find_members


[docs]
 1class UnionFindMembers:
 2
 3    def __init__(self, n: int) -> None:
 4        self._n: int = n
 5        self._group_count: int = n
 6        self._group: list[list[int]] = [[i] for i in range(n)]
 7

[docs]
 8    def unite(self, x: int, y: int) -> bool:
 9        u = self._group[x]
10        v = self._group[y]
11        if u is v:
12            return False
13        self._group_count -= 1
14        if len(u) > len(v):
15            u, v = v, u
16        for i in u:
17            v.append(i)
18            self._group[i] = v
19        return True

20

[docs]
21    def size(self, x: int) -> int:
22        """Return xが属する集合の要素数. / O(1)"""
23        return len(self._group[x])

24

[docs]
25    def same(self, x: int, y: int) -> bool:
26        """Return True if 'same' else False. / O(1)"""
27        return self._group[x] is self._group[y]

28

[docs]
29    def members(self, x: int) -> list[int]:
30        """Return set(the members of x). / O(1)"""
31        return self._group[x]

32

[docs]
33    def group_count(self) -> int:
34        """Return the number of groups. / O(1)"""
35        return self._group_count