差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン前のリビジョン | 次のリビジョン両方とも次のリビジョン | ||
programming_algorithm:data_structure:union_find_tree [2019/09/21] – [実装] ikatakos | programming_algorithm:data_structure:union_find_tree [2020/05/07] – [実装] ikatakos | ||
---|---|---|---|
行 92: | 行 92: | ||
* '' | * '' | ||
* ついでに経路圧縮を行う | * ついでに経路圧縮を行う | ||
+ | |||
+ | < | ||
<sxh python> | <sxh python> | ||
行 103: | 行 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): | ||
行 148: | 行 152: | ||
def _root(self, x): | def _root(self, x): | ||
- | | + | |
- | | + | tbl = self.table |
- | | + | while tbl[x] >= 0: |
- | | + | |
- | return | + | x = tbl[x] |
+ | | ||
+ | | ||
+ | return x | ||
def find(self, x, y): | def find(self, x, y): |