So... am I misunderstanding or is it enough to swap the iteration over the neighbours of a node and the visited check?

          for nbr in graph[node]:
            if not visited[nbr]:

into

          if node in visited: continue
          visited.add(node)
          for nbr in graph[node]:
              stack.append(nbr)