algorithm - 将 LCA 解决方案从树扩展到 DAG

Question

我正在使用使用 RMQ 在树中解决 LCA 的算法。

它基本上是这样工作的：

• 我们在树上执行欧拉之旅，得到 3 个数组

  E = {0,1,0,2,0} //the vertexes in the order they were visited
  L = {0,1,0,1,0} //the levels of each of these vertexes
  I = {0,1,3}     //index of the first ocurrence of each vertex
  

• 如果我们想要LCA(u,v)，我们只需要获取LfromI[u]到的 RMQ I[v]。

I[1] = 1例如： LCA(1,2) = 从索引到的 L 的 RMQ I[2] = 3。

L[1:3] = [1,0,1], RMQ[1,0,1] = 0，即索引 2，因此LCA(1,2) = E[2] = 0。

---

我的问题是：如何扩展此解决方案以适应有向无环图？

就这样，行不通。假设我们有这个 DAG：

如果我们计算E,L和I，我们将有：

E = {0,1,3,1,4,1,0,2,4,2,5,2,0}
L = {0,1,2,1,2,1,0,1,2,1,2,1,0}
I = {0,1,7,2,4,10}

并且可以看出它是错误的证明计算 LCA(2,4)，这显然应该是 2，因为 2 是 4 的父级，但是按照算法，我们将计算：

RMQ( I[2] : I[4] ) = RMQ(7,4) = RMQ(4,7) = RMQ( {2,1,0,1} ) = 0

0 有索引 6，所以LCA(2,4) = E[6] = 0，这是错误的。

有没有办法让它工作？

标签： algorithmtreedirected-acyclic-graphsrmqlowest-common-ancestor