如何在有向无环图中找到多个节点的最不祖先？
我已经找到了很多关于该主题的论文，但他们似乎都在DAG中为two节点找到了LCA。
是否有针对多个节点的好的算法？
也许您也可以采用适用于DAG的方式修改用于树的算法。
如您所知，对于每个查询，存在一种算法，该算法可通过O（nlgn）预处理和O（1）预处理在树中找到LCA，因此可找到k] >节点需要O（k）。有关此算法的更多详细信息，请参见here。正如@ DennisMeng，@ vzn和@ user824425在评论中已经指出的，在某些情况下（！），可以通过（二进制）LCA运算符的逐对递归应用]计算两个以上节点的LCA。例如：