2011-09-06から1日間の記事一覧
4-3 「グラフマスターへの道」の続きです。 LCA (Lowest Common Ancestor) - 根つき木の2つのノードの共通の祖先で最も近いもの 二分探索を用いて探索 木の深さに注目して、注目点の深さの均等にしつつ親を探索していくと O(n) いったん LCA に到達すれば後…
4-3 「グラフマスターへの道」の続きです。 LCA (Lowest Common Ancestor) - 根つき木の2つのノードの共通の祖先で最も近いもの 二分探索を用いて探索 木の深さに注目して、注目点の深さの均等にしつつ親を探索していくと O(n) いったん LCA に到達すれば後…