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