DAG上のLCAは一意ではない(ことがある)

#programming #algorithm

今日とある問題について考えた結果、DAG上の最小共通祖先(LCA)問題に帰着することができた。

木構造上のLCAは競プロでいくつか見たことある。これで解けたも同然だと浮かれて「DAG LCA」とTwitter検索をかけたら、『DAG上のLCAは定義できない』と言っている人がいた。

ほんとに……？

悲しいことに、めちゃくちゃ考えてもDAG上のLCAが曖昧になる(2つ以上のノードとなる)例を挙げることができず、最終的に英Wikipediaの記事にたどり着いた。 この例を簡単に思いつけなかった反省に、実例を記す。

LCAが唯一見つかる例

graph
    A --> B
    A --> C
    C --> D
    A --> D
    B --> E
    B --> D
    E --> F
    D --> G

このようなグラフ上で、 LCA(F, G) = B である。

LCAが見つからない例

graph
    A --> C
    B --> C

このようなグラフ上で、 LCA(A, B) は存在しない。

LCAが曖昧になる例

graph
    A --> X
    A --> Y
    B --> X
    B --> Y

このようなグラフ上で、 LCA(X, Y) は AまたはBである。

今回の用途では、LCAが見つからなかったり曖昧であるときの動作を定義することができるので、この実例自体は問題にはならなかった。 具体的なアルゴリズムは、Wikipediaにいくつかリンクが貼られているので、明日検討しよう。