< Back





1466. Reorder Routes to Make All Paths Lead to the City Zero

Unlike regular connectivity problems, we're asked to handle a graph with directed edges. We need to
find the number of edges that have to be reversed in order to make all edges lead to the 0th city.
To intuitively solve this, we'll conduct a depth-first search from the 0th node. Depth-first search
is inherently directed away from the node it starts from.

We keep track of the edges present in the input, maintaining their direction. Each time we visit a
node, we're traveling away from the 0th node. So if we encounter an edge that's traveling in the
same direction, away, we know that this edge needs to be reversed - we increment our counter.

The solution is as follows:


  from collections import defaultdict

  class Solution:
      def minReorder(self, n: int, connections: List[List[int]]) -> int:
          roads = set()
          graph = defaultdict(list)
          for x, y in connections:
              graph[x].append(y)
              graph[y].append(x)
              roads.add((x, y))

          def dfs(node: int) -> int:
              ans = 0

              for neighbor in graph[node]:
                  if neighbor not in seen:
                      if (node, neighbor) in roads:
                          ans += 1
                      seen.add(neighbor)
                      ans += dfs(neighbor)

              return ans

          seen = {0}
          return dfs(0)


_ Time Complexity:

  O(n) - We visit each node once.

_ Space Complexity:

  O(n) - We maintain an adjaceny list.