差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン | 次のリビジョン両方とも次のリビジョン | ||
| programming_algorithm:data_structure:union_find_tree [2021/01/31] – ikatakos | programming_algorithm:data_structure:union_find_tree [2021/01/31] – [実装] ikatakos | ||
|---|---|---|---|
| 行 84: | 行 84: | ||
| * ${\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> | ||
| 行 99: | 行 99: | ||
| self.table = [-1] * n | self.table = [-1] * n | ||
| - | def _root(self, x): | + | def root(self, x): |
| stack = [] | stack = [] | ||
| tbl = self.table | tbl = self.table | ||
| 行 110: | 行 110: | ||
| def find(self, x, y): | def find(self, x, y): | ||
| - | return self._root(x) == self._root(y) | + | return self.root(x) == self.root(y) |
| - | def union(self, x, y): | + | def unite(self, x, y): |
| - | r1 = self._root(x) | + | r1 = self.root(x) |
| - | r2 = self._root(y) | + | r2 = self.root(y) |
| if r1 == r2: | if r1 == r2: | ||
| return | return | ||
| 行 130: | 行 130: | ||
| if __name__ == ' | if __name__ == ' | ||
| ins = UnionFind(4) | ins = UnionFind(4) | ||
| - | ins.union(0, 1) | + | ins.unite(0, 1) |
| - | ins.union(2, 3) | + | ins.unite(2, 3) |
| print(ins.find(0, | print(ins.find(0, | ||
| - | ins.union(1, 2) | + | ins.unite(1, 2) |
| print(ins.find(0, | print(ins.find(0, | ||
