差分

このページの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:
   * ''_root''で代表を再帰的に探索する   * ''_root''で代表を再帰的に探索する
     * ついでに経路圧縮を行う     * ついでに経路圧縮を行う
 +
 +<note> 2020/05 _rootを非再帰に変更(特にPyPyで高速化) </note>
  
 <sxh python> <sxh python>
行 103: 行 105:
  
     def _root(self, x):     def _root(self, x):
-        if self.table[x] 0: +        stack = [] 
-            return +        tbl = self.table 
-        else+        while tbl[x] >= 0: 
-            # 経路の圧縮 +            stack.append(x
-            self.table[x] = self._root(self.table[x]) +            x = tbl[x] 
-            return self.table[x]+        for y in stack
 +            tbl[y] = x 
 +        return x
  
     def find(self, x, y):     def find(self, x, y):
行 148: 行 152:
  
     def _root(self, x):     def _root(self, x):
-        if self.table[x] 0: +        stack = [] 
-            return +        tbl = self.table 
-        else+        while tbl[x] >= 0: 
-            self.table[x] = self._root(self.table[x]) +            stack.append(x
-            return self.table[x]+            x = tbl[x] 
 +        for y in stack
 +            tbl[y] = x 
 +        return x
  
     def find(self, x, y):     def find(self, x, y):
programming_algorithm/data_structure/union_find_tree.txt · 最終更新: 2020/05/07 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0