Проверка на достижимость в направленном графе?

Question

[floppa322]

Почитал статью в вики по достижимости в направленных графах. Алгоритмы, представленные в статье, либо тратят > O(n) на препроцессинг, либо требуют от графа много свойств, например,

An even faster method for pre-processing, due to T. Kameda in 1975,[7] can be used if the graph is planar, acyclic, and also exhibits the following additional properties: all 0-indegree and all 0-outdegree vertices appear on the same face

.

Не понимаю, почему, нельзя сделать следующим образом:
1. Найти конденсацию графа O(n) препроцессинга
2. Для конденсации построить структуру для нахождения LCA для За O(n) / O(nlogn) препроцессинга

Запрос будет выполняться за O(1) / O(logn) в зависимости от того, что используется для нахождения LCA:
1. Проверить, что u и v, находятся в одной SCC - O(1). Если да, то true, иначе сделать шаг 2
2. Проверить, что u и v находятся в одном DAG'е - O(1). Если нет, то false, иначе сделать шаг 3
3. Проверить, что LCA у u(from) и v (to) равен u (то есть они на одном пути от корня) - O(1) / O(logn), если да, то true, иначе false



Картинка для пояснения: для u, v - false, для u штрих,v штрих - true

Answer 1

[floppa322]

Кажется нашёл проблему: алгоритм выше неправильно работает при наличии перекрёстных рёбер :(
Например, если было бы ребро из 10 в 5

Answer 2

[Wataru]

Под конденсацией вы подразумеваете сжатие компонент сильной связности? Ну так у вас остается в конце какой-то произвольный DAG, а не дерево.

В нем уже нельзя ввести поняие LCA вообще. Например, граф 0->2, 0->3, 1->2, 1->3. Тут для вершин 2 и 3 есть два общих предка: 0 и 1. И какой из них самый нижний?

Comments

[floppa322]

да, я не учёл наличие красных рёбер (из картинки выше), нужно как-то это тоже проверять, боюсь, что таким образом приду как раз к тем двум алгоритмам из той статьи - Thorup's Algorithm и Kameda's Algorithm

[floppa322]

Вообще можно было бы попробовать бин поиском (по timeIn dfs) по вершинам, в которые можно по перекрёстным рёбрам добраться(как 4-й шаг в том алгоритме): скакать по вершинам, используя timeIn вершины to, и при каждом переходе в перекрёстную вершину, проверять timeIn у to > или <, чем, timeIn перекрёстной вершины, ну то есть выше или ниже она дереве обхода dfs

Хотя такое, наверное не сделать, лучше чем за n*logn памяти, а это многовато