1466. Reorder Routes to Make All Paths Lead to The City Zero - Explanation

Problem Link

1. Depth First Search - I

Intuition

We need all cities to reach city 0, so we traverse outward from city 0 and check edge directions. Build an undirected neighbors graph for traversal, but store original edges in edges set to check direction. When moving from city A to neighbor B, if the original edge goes from A to B (away from 0), it needs to be reversed. dfs ensures we visit every city exactly once.

Algorithm

1. Store all original directed edges in a set called edges as (a, b) pairs.
2. Build an adjacency list called neighbors treating edges as undirected.
3. Start dfs from city 0, marking visited cities in visit set.
4. For each neighbor:
   • If not visited, check if (neighbor, city) exists in the edges set.
   • If not, the edge points away from 0 and needs reversal; increment changes.
   • Recursively visit the neighbor.
5. Return the total count of edges to reverse.

class Solution:
    def minReorder(self, n: int, connections: List[List[int]]) -> int:
        edges = {(a, b) for a, b in connections}
        neighbors = {city: [] for city in range(n)}
        visit = set()
        changes = 0

        for a, b in connections:
            neighbors[a].append(b)
            neighbors[b].append(a)

        def dfs(city):
            nonlocal changes
            visit.add(city)
            for neighbor in neighbors[city]:
                if neighbor in visit:
                    continue
                if (neighbor, city) not in edges:
                    changes += 1
                dfs(neighbor)

        dfs(0)
        return changes

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$

---

2. Depth First Search - II

Intuition

Instead of using a separate set to track edge directions, we can encode direction information directly in the adjacency list. When adding edges, we store the original direction as a positive value and the reverse as negative. During dfs, positive nei values indicate edges pointing away from city 0, which need reversal.

Algorithm

1. Build an adjacency list called adj where each edge (u, v) adds v to adj[u] and -u to adj[v].
2. Start dfs from city 0 with parent = -1.
3. For each nei (neighbor):
   • Skip if abs(nei) equals the parent (to avoid going back).
   • Add 1 to the count if nei > 0 (edge needs reversal).
   • Recursively process abs(nei) as the next node.
4. Return the total count.

class Solution:
    def minReorder(self, n: int, connections: List[List[int]]) -> int:
        adj = [[] for _ in range(n)]
        for u, v in connections:
            adj[u].append(v)
            adj[v].append(-u)

        def dfs(node, parent):
            changes = 0
            for nei in adj[node]:
                if abs(nei) == parent:
                    continue
                changes += dfs(abs(nei), node) + (nei > 0)
            return changes

        return dfs(0, -1)

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$

---

3. Breadth First Search

Intuition

bfs works equally well since we just need to visit all nodes once from city 0. We store each edge with a flag isForward indicating if it is a forward edge (pointing away from city 0). Processing level by level in queue, whenever we traverse a forward edge, we count it as needing reversal.

Algorithm

1. Build an adjacency list called adj where each edge (u, v) stores (v, 1) in adj[u] and (u, 0) in adj[v].
2. Initialize a queue with city 0 and mark it visited in visit array.
3. While the queue is not empty:
   • Dequeue a node.
   • For each unvisited neighbor, mark it visited, add isForward to the count, and enqueue it.
4. Return the total count.

class Solution:
    def minReorder(self, n: int, connections: List[List[int]]) -> int:
        adj = [[] for _ in range(n)]
        for u, v in connections:
            adj[u].append((v, 1))
            adj[v].append((u, 0))

        visit = [False] * n
        queue = deque([0])
        visit[0] = True
        changes = 0

        while queue:
            node = queue.popleft()
            for neighbor, isForward in adj[node]:
                if not visit[neighbor]:
                    visit[neighbor] = True
                    changes += isForward
                    queue.append(neighbor)
        return changes

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$

---

Common Pitfalls

Treating the Graph as Directed Only

A common mistake is building only a directed adjacency list based on the given edges. Since we need to traverse the entire tree starting from city 0, we must treat edges as undirected for traversal purposes while separately tracking the original direction to count reversals.

Reversing the Logic of Edge Direction Check

When checking if an edge needs reversal, it is easy to get the condition backwards. Remember that edges pointing away from city 0 need reversal. If traversing from node A to neighbor B and the original edge is (A, B), it points away from 0 and must be counted; if the original edge is (B, A), it already points toward 0.

Not Handling the Sign Encoding for Node 0

In the DFS-II approach that uses negative values to encode direction, node 0 cannot be represented as negative since -0 == 0. This edge case must be handled by using the parent check (abs(nei) == parent) rather than relying solely on sign for all nodes.