差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
programming:algorithm:data_structure:union_find_tree [2017/08/09] – [高速化の工夫] ikatakos | programming_algorithm:data_structure:union_find_tree [2020/05/07] – [実装] 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$個のグループに所属している状態 | ||
* '' | * '' | ||
* ついでに経路圧縮を行う | * ついでに経路圧縮を行う | ||
+ | |||
+ | < | ||
<sxh python> | <sxh python> | ||
行 102: | 行 105: | ||
def _root(self, x): | def _root(self, x): | ||
- | | + | |
- | | + | tbl = self.table |
- | | + | while tbl[x] >= 0: |
- | | + | |
- | self.table[x] = self._root(self.table[x]) | + | x = tbl[x] |
- | return | + | |
+ | | ||
+ | return x | ||
def find(self, x, y): | def find(self, x, y): | ||
行 136: | 行 141: | ||
print(ins.find(0, | print(ins.find(0, | ||
+ | </ | ||
+ | |||
+ | 統合時、どちらを根にするかの基準をグループの深さで無く「要素数」とした実装。unionの部分が少し変化。 | ||
+ | |||
+ | <sxh python> | ||
+ | |||
+ | class UnionFind: | ||
+ | def __init__(self, | ||
+ | self.table = [-1] * n | ||
+ | |||
+ | def _root(self, x): | ||
+ | stack = [] | ||
+ | tbl = self.table | ||
+ | while tbl[x] >= 0: | ||
+ | stack.append(x) | ||
+ | x = tbl[x] | ||
+ | for y in stack: | ||
+ | tbl[y] = x | ||
+ | return 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] += d1 | ||
</ | </ |