Проблема: аргумент по умолчанию `visited=set()` создаётся один раз при определении функции и пересчитывается между вызовами. Поэтому при повторных вызовах ранее отмеченные вершины остаются в множестве — обход будет неполным/неправильным.
Почему: Python использует один и тот же объект-мутируемый по умолчанию для всех вызовов функции.
Исправление (стандартный приём — использовать `None` и инициализировать внутри):
def dfs(v, visited=None):
if visited is None:
visited = set()
visited.add(v)
for u in graph[v]:
if u not in visited:
dfs(u, visited)
Альтернативы: требовать явной передачи `visited` при внешних вызовах или держать `visited` как локальную структуру и возвращать её.