union_find_members¶
ソースコード¶
from titan_pylib.data_structures.union_find.union_find_members import UnionFindMembers
展開済みコード¶
1# from titan_pylib.data_structures.union_find.union_find_members import UnionFindMembers
2class UnionFindMembers:
3
4 def __init__(self, n: int) -> None:
5 self._n: int = n
6 self._group_count: int = n
7 self._group: list[list[int]] = [[i] for i in range(n)]
8
9 def unite(self, x: int, y: int) -> bool:
10 u = self._group[x]
11 v = self._group[y]
12 if u is v:
13 return False
14 self._group_count -= 1
15 if len(u) > len(v):
16 u, v = v, u
17 for i in u:
18 v.append(i)
19 self._group[i] = v
20 return True
21
22 def size(self, x: int) -> int:
23 """Return xが属する集合の要素数. / O(1)"""
24 return len(self._group[x])
25
26 def same(self, x: int, y: int) -> bool:
27 """Return True if 'same' else False. / O(1)"""
28 return self._group[x] is self._group[y]
29
30 def members(self, x: int) -> list[int]:
31 """Return set(the members of x). / O(1)"""
32 return self._group[x]
33
34 def group_count(self) -> int:
35 """Return the number of groups. / O(1)"""
36 return self._group_count