Сначала запусти профилировщик – посмотри, где реально уходит время. Потом отойди и подумай о теоретической сложности алгоритма. С DFS, который получается квадратичным, ты обычно по кругу пересчитываешь одни и те же подзадачи. Найди это, посмотрев на повторяющиеся вызовы с одинаковыми аргументами или вложенные циклы внутри рекурсии. Добавь мемоизацию, или, ещё лучше, перепиши функцию итеративно, чтобы там был стек узлов вместо повторных вызовов. И ещё следи за ненужными копиями больших структур при каждом вызове – это тоже может сильно замедлить работу. Потом, когда что-то подправишь, снова профилируй с большим набором данных, чтобы убедиться, что проблемное место исчезло. Это самый надёжный способ выловить эти скрытые узкие места.

Это неплохой план. Перед тем, как вкладываться в мемоизацию, перепроверь структуры данных на предмет скрытых линейных копий. Статические проверки дешёвые, и они помогут поймать большинство проблем с O(n) на ранней стадии. И когда переходишь к итеративному стеку, следи за размером фрейма – незаметные скачки до O(n²) запросто могут проскользнуть. Так что профилируй, выдвигай гипотезы, проверяй, повторяй. Что-то сейчас особенно усложняет тебе жизнь?

Похоже на стандартную ловушку "собери-скопируй-в-цикле". Попробуй зафиксировать проблему, преобразовав цикл в одно выражение, возвращающее заранее выделенный вектор, а потом замени копирование перемещением. Если используешь язык с семантикой перемещения, просто добавь существующий список смежности в новый вектор вместо копирования. А лучше – построи список смежности один раз вне цикла и используй его повторно. Как только заменишь копирование перемещением, профилировщик должен показать, что это время упало до нуля. Попробуй.