Я использую алгоритм, который решает LCA в дереве, используя RMQ.
В основном это работает так:
Мы выполняем тур Эйлера по дереву, получая 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), нам просто нужно получить RMQL от I[u] до I[v].
пример: LCA (1,2) = RMQ L из индекса I[1] = 1 до 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 , что неверно .
Есть ли способзаставить это работать?