c++ - 最低共同祖先( boost 图)

Question

boost 中是否有内置方法来查找树中两个或多个节点的最低公共(public)祖先(这是一个 boost::graph 实例)？

如果没有，我将不胜感激有关执行此操作的最佳方法的建议。 Wikipedia claims有有效的算法可以在 O(1) 时间内实现这一点(使用 O(n) 预处理)，但它没有描述算法。

Answer 1

在Wikipedia中找到算法:

 function TarjanOLCA(u)
 MakeSet(u);
 u.ancestor := u;
 for each v in u.children do
     TarjanOLCA(v);
     Union(u,v);
     Find(u).ancestor := u;
 u.colour := black;
 for each v such that {u,v} in P do
     if v.colour == black
         print "Tarjan's Least Common Ancestor of " + u +
               " and " + v + " is " + Find(v).ancestor + ".";