我的问题的答案可能很明显，而且我在纸上知道这个明显的答案。我的意思是，当涉及到一些示例时，我理解为什么我们不允许使用循环来运行最低公共祖先算法，但是我在理解为解决 DAG 中的 LCA 而编写的论文时遇到了问题。所以解决方案的哪一部分阻止我们在循环图上使用它..
我愿意知道并且很感激被告知：
在我的问题中，找到它们的 LCA 的节点对不在一个循环内，所以我认为可能有一种方法可以解决这个问题。
提前致谢
循环的问题始于定义本身。
u和的 LCAv被定义为一组这样的节点z，这些节点z可以从u和到达，v并且z不能从任何其他节点到达，z'这样z'可以从u和到达v。
它可能不存在于循环图中。例如，如果有一个循环1->2->3和两个其他节点和边：4->3and 5->3，则 and 没有 LCA 4（5因为所有1, 2and3都可以从它们两者中访问，但它们也可以相互访问）。
u您可以找到所有可以从and到达的节点v（使用 dfs 或其他东西），然后检查是否有这样一个节点z可以从它们两个都可以到达，但不能从满足此条件的任何其他节点（它可以在多项式中工作）时间）。
所以它更多的是关于对最低共同祖先进行有意义的定义，而不是能够计算它（如我上面所示，你可以计算类似的东西，但即使对于不在同一个节点上的两个节点也可能没有意义循环）。