Здравствуйте, пусть дана задача нахождения наименьшего общега предка в дереве, допустим в оффлайне, тогда логично писать классический алгоритм Тарьяна. Вопрос как его можно модифицировать для работы на лесе, когда у некоторых вершин может не быть LCA.

Я вижу 2 варианта:

1) завести дополнительные непересекащиеся множества component[N], положить туда леса, перед выводом LCA проверять что они лежат в одном множестве find(component[a]) == find(component[b]), при этом трачу дополнительно N памяти, N времени и строчек 15 кода.

2) Сделать фиктивную вершину, провести из нее ребра во все корни деревьев в лесу. Тогда нужно найти корни, чаще всего опять для этого нужно N памяти, при этом легче ошибиться при построении и т.д. В итоге та же память, может быть только строчек будет 10, а не 15.

Есть ли более красивые варианты как модифицировать LCA, для работы на лесе?