差分

このページの2つのバージョン間の差分を表示します。

この比較画面へのリンク

両方とも前のリビジョン前のリビジョン
次のリビジョン両方とも次のリビジョン
programming_algorithm:graph_theory:lowest_common_ancestor [2019/11/29] – [EulerTour + RMQ] ikatakosprogramming_algorithm:graph_theory:lowest_common_ancestor [2019/11/29] – [EulerTour + RMQ] ikatakos
行 50: 行 50:
 ===オイラーツアーを用いたLCA=== ===オイラーツアーを用いたLCA===
  
-LCAを求めるには、オイラーツアーで通りかかった順番に頂点と深さを記録していく。また、その過程で以下の情報も記録していく。+LCAを求めるには、オイラーツアーで通りかかった順番に頂点と深さを記録していく。また、その過程で各頂点が最初に現れた位置も記録していく。
  
   * ''eular_tour[i] = (d, v)''   * ''eular_tour[i] = (d, v)''
     * $i$ 番目に通りかかる頂点の(深さ, 頂点番号)     * $i$ 番目に通りかかる頂点の(深さ, 頂点番号)
-  * ''depth[v] = d'' 
-    * 頂点 $v$ の深さ 
   * ''first_appear[v] = i''   * ''first_appear[v] = i''
     * 頂点 $v$ がeular_tour上で初めて現れるindex     * 頂点 $v$ がeular_tour上で初めて現れるindex
行 63: 行 61:
      1  2                v: 0, 1, 3, 5, 3, 1, 4, 1, 0, 2, 0]      1  2                v: 0, 1, 3, 5, 3, 1, 4, 1, 0, 2, 0]
     / \     / \
-   3 4     depth = [0, 1, 1, 2, 2, 3] +   3 4     first_appear = [0, 1, 9, 2, 6, 3] 
-   |        first_appear = [0, 1, 9, 2, 6, 3]+   |
    5    5
  
programming_algorithm/graph_theory/lowest_common_ancestor.txt · 最終更新: 2020/05/10 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0