Рассмотрим ориентированный граф , на котором можно динамически добавлять края и сделать некоторые конкретные запросы.
Пример: непересекающееся-множество лесов
Рассмотрим следующий набор запросов:
arrow(u, v)
equiv(u, v)
find(u)
первый добавляет стрелку к графу, второй решает, если , последний находит канонического представителя класса эквивалентности , то есть a такого что подразумевает .u ↔ ∗ v ↔ ∗ r ( u ) u ↔ ∗ v r ( v ) = r ( u )
Существует хорошо известный алгоритм с использованием структуры данных лесов непересекающейся-набором , реализующую эти запросы в квазипостоянном амортизируется, а именно сложность . Обратите внимание , что в данном случае реализуется с помощью .equiv
find
Более сложный вариант
Теперь меня интересует более сложная проблема, где направления имеют значение:
arrow(u, v)
confl(u, v)
find(u)
первый добавляет стрелку , секунд решает, есть ли узел достижимый как от и от , т.е. . Последний должен возвращать объект такой, что подразумевает где должен легко вычисляться. (Для того, чтобы, скажем, вычислить ). Цель состоит в том, чтобы найти хорошую структуру данных, чтобы эти операции выполнялись быстро.confl
циклы
Граф может содержать циклы.
Я не знаю, есть ли способ эффективно и постепенно вычислять сильно связанные компоненты, чтобы рассматривать DAG только для основной проблемы.
Конечно, я был бы признателен за решение для DAG. Это будет соответствовать инкрементному вычислению наименее общего предка.
Наивный подход
Структура данных леса с несвязным множеством здесь не помогает, так как она игнорирует направление ребер. Обратите внимание, что не может быть одним узлом, если граф не является слитым.
Можно определить и определить как когда . Но как вычислить это постепенно?∙ S 1 ∙ S 2 S 1 ∩ S 2 ≠ ∅
Вероятно, что вычисление такого большого набора бесполезно, меньший набор должен быть более интересным, как в обычном алгоритме поиска объединения.
confl(u,v)
find
find
find