UnionFind
のコードを修正しています。
あるデータ(辺)x
の属する集合(木)の根を求めるメソッドをget_size(self, x)
, すべての根をset
として返すものをget_groups(self)
と定義してあります。
色々な命名規則を読んでいるとget
, set
はgetter
, setter
に使うのが一般的で、他に使うと混乱を招く...とされているように感じます。
この場合は、get
の代わりにどういう動詞を使うべきなのでしょうか?
Python
1from typing import Set 2 3 4class UnionFind: 5 __slots__ = ["_data_size", "_first_index", "_parents"] 6 7 def __init__(self, data_size: int, is_zero_indexed: bool = True) -> None: 8 self._data_size = data_size 9 self._first_index = 0 if is_zero_indexed else 1 10 self._parents = [-1] * (data_size + self._first_index) 11 12 def find(self, x: int) -> int: 13 """Find the group (root) of vertex x""" 14 if self._parents[x] < 0: 15 return x 16 self._parents[x] = self.find(self._parents[x]) 17 return self._parents[x] 18 19 def is_connected(self, x: int, y: int) -> bool: 20 """Return whether two vertices x and y are connected or not.""" 21 return self.find(x) == self.find(y) 22 23 def unite(self, x: int, y: int) -> None: 24 """Unite two groups of vertices x and y.""" 25 x, y = self.find(x), self.find(y) 26 if x == y: 27 return 28 if self._parents[x] > self._parents[y]: 29 x, y = y, x 30 self._parents[x] += self._parents[y] 31 self._parents[y] = x 32 33 def get_size(self, x: int) -> int: 34 """Return the size of the group vertex x belongs.""" 35 return -self._parents[self.find(x)] 36 37 def get_groups(self) -> Set[int]: 38 """Return the set of groups (roots).""" 39 return { 40 self.find(x) 41 for x in range(self._first_index, self._data_size + self._first_index) 42 } 43 44 def count_groups(self) -> int: 45 """Count the number of groups (roots).""" 46 return len(self.get_groups())
回答1件
あなたの回答
tips
プレビュー