差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン | 次のリビジョン両方とも次のリビジョン | ||
| programming_algorithm:data_structure:union_find_tree [2017/10/08] – ↷ programming:algorithm:data_structure:union_find_tree から programming_algorithm:data_structure:union_find_tree へページを移動しました。 ikatakos | programming_algorithm:data_structure:union_find_tree [2019/08/25] – ikatakos | ||
|---|---|---|---|
| 行 1: | 行 1: | ||
| ======Union-Find木====== | ======Union-Find木====== | ||
| - | * 要素が$n$個ある | + | |
| - | * 各要素は互いに素なグループに1つだけ属する | + | |
| - | * 例: 生徒は必ず何かのクラブ活動に入り、かつ、兼部は認められていない | + | |
| - | * グループは統合される可能性がある。分割はされない | + | * 例: 生徒は必ず何かのクラブ活動に入り、兼部は認められていない |
| + | * グループは統合される可能性があるが、分割はされない | ||
| という前提で、 | という前提で、 | ||
| 行 85: | 行 86: | ||
| =====実装===== | =====実装===== | ||
| - | * 要素数$n$の配列'' | + | * 要素数 $n$ の配列'' |
| - | * ${\rm table}[x]$が負ならば、$x$は代表。絶対値はランクを示す | + | * ${\rm table}[x]$ が負ならば、$x$ は代表。絶対値はランクを示す |
| - | * ${\rm table}[x]$が非負ならば、$x$は代表でない。値は$x$の親を示す | + | * ${\rm table}[x]$ が非負ならば、$x$ は代表でない。値は $x$ の親を示す |
| * 最初は、$n$個の要素が別々の$n$個のグループに所属している状態 | * 最初は、$n$個の要素が別々の$n$個のグループに所属している状態 | ||
| * '' | * '' | ||
| 行 136: | 行 137: | ||
| print(ins.find(0, | print(ins.find(0, | ||
| + | </ | ||
| + | |||
| + | 統合時、どちらを根にするかの基準をグループの深さで無く「要素数」とした実装。unionの部分が少し変化。 | ||
| + | |||
| + | <sxh python> | ||
| + | |||
| + | class UnionFind: | ||
| + | def __init__(self, | ||
| + | self.table = [-1] * n | ||
| + | |||
| + | def _root(self, x): | ||
| + | if self.table[x] < 0: | ||
| + | return x | ||
| + | else: | ||
| + | self.table[x] = self._root(self.table[x]) | ||
| + | return self.table[x] | ||
| + | |||
| + | def find(self, x, y): | ||
| + | return self._root(x) == self._root(y) | ||
| + | |||
| + | def union(self, x, y): | ||
| + | r1 = self._root(x) | ||
| + | r2 = self._root(y) | ||
| + | if r1 == r2: | ||
| + | return | ||
| + | d1 = self.table[r1] | ||
| + | d2 = self.table[r2] | ||
| + | if d1 <= d2: | ||
| + | self.table[r2] = r1 | ||
| + | self.table[r1] += d2 | ||
| + | else: | ||
| + | self.table[r1] = r2 | ||
| + | self.table[r2] = r1 | ||
| </ | </ | ||
