Здравствуйте, пусть дана задача нахождения наименьшего общега предка в дереве, допустим в оффлайне, тогда логично писать классический алгоритм Тарьяна. Вопрос как его можно модифицировать для работы на лесе, когда у некоторых вершин может не быть LCA.
Я вижу 2 варианта:
1) завести дополнительные непересекащиеся множества component[N], положить туда леса, перед выводом LCA проверять что они лежат в одном множестве find(component[a]) == find(component[b]), при этом трачу дополнительно N памяти, N времени и строчек 15 кода.
2) Сделать фиктивную вершину, провести из нее ребра во все корни деревьев в лесу. Тогда нужно найти корни, чаще всего опять для этого нужно N памяти, при этом легче ошибиться при построении и т.д. В итоге та же память, может быть только строчек будет 10, а не 15.
Есть ли более красивые варианты как модифицировать LCA, для работы на лесе?
Не надо ничего заводить, просто запустить алгоритм Тарьяна для каждого из деревьев. Оно автоматически оставит неотвеченными какие-то запросы, вот там и не будет LCA.
Ну если предыдущие будут посещены, то алгоритм Тарьяна найдет то, что это вершина входит в запрос, а другая вершина из этого запроса была посещена и выдаст ответ. Там же проверка посещена ли вершина для запроса, если да, то выдаст ответ.
Очищать use пометки тоже не вариант, т.к. иногда корень искать отдельно не хочется, а хочется идти по массиву, проверять use и запускать dfs, если не использована. P.s. для точности, пользуюсь алгоритмом http://e-maxx.ru/algo/lca_linear_offline
Не нужно очищать массив used. Достаточно изменить bool на int и для каждой компоненты связности увеличивать значение изменения used на 1 (для первой компоненты красим used единицами, для второй компоненты двойками и т.д.) — стандартный прием. Тогда запускаемся, если used = 0, и отвечаем на запрос, если цвета совпадают (в одной компоненте связности).
Тогда нужно искать корни по массиву, т.е. если в задаче на вход задано дерево, то мы можем не знать где корень, просто пройтись по всем вершинам, заходя в не использованные. А в случае леса придется вычислять корни и идти по ним. Т.е. как в способе 2). Не сильно сложно, но неприятно.
Корни — вершины без входящих ребер. То есть можно при считывании считать массив degree. И запускаться от тех, у кого degree = 0.
На e-maxx данная реализация предполагает, что 0 — это корень дерева. Поэтому ничего не приходится искать.
Как вы собираетесь запускать dfs, не найдя какие вершины являются корнями? Нельзя запускать последовательно из всех еще не посещенных вершин.
Контрпример: Дерево из трех вершин, 2-я вершина корень, 0-я и 1-я вершины подвешены к 2й. (То есть вот такие ребра 2 -> 0, 2 -> 1). Нужно найти LCA(0, 1).
Согласен, был не прав, вопрос закрыт.