1

我正在使用使用 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，这是错误的。

有没有办法让它工作？

4

0 回答 0