Reorder Routes to Make All Paths Lead to the City Zero

How it works

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.

Steps

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.

Complexity

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

Things to watch for

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.

from typing import List
from collections import deque

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

class Solution {
public:
    int minReorder(int n, vector<vector<int>>& connections) {
        vector<vector<pair<int, int>>> adj(n);
        for (auto& conn : connections) {
            adj[conn[0]].push_back({conn[1], 1});
            adj[conn[1]].push_back({conn[0], 0});
        }

        vector<bool> visit(n, false);
        queue<int> q;
        q.push(0);
        visit[0] = true;
        int changes = 0;

        while (!q.empty()) {
            int node = q.front();
            q.pop();
            for (auto& [neighbor, isForward] : adj[node]) {
                if (!visit[neighbor]) {
                    visit[neighbor] = true;
                    changes += isForward;
                    q.push(neighbor);
                }
            }
        }
        return changes;
    }
};