Почему это работает
- Обход в глубину из данного узла доходит до каждого узла связного графа, и clone(node) копирует каждый, до которого дошёл.
- По циклу обход возвращается к узлу, который уже начал копировать, а до узла можно дойти с двух сторон, как до 3 здесь. Словарь «старый → копия» заполняется до обхода соседей, поэтому такой узел в нём уже есть и его копия берётся оттуда: без второй копии и без бесконечного круга.
- Каждый сосед копии — это то, что вернул clone, а clone возвращает только копии, поэтому ни одна ссылка копии не ведёт в старый граф.
Сложность
Время O(V + E): каждый узел копируем один раз, каждое ребро смотрим с двух концов. Память O(V): словарь и стек вызовов глубиной до V.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗