Code Implementation

class Solution:
    def minReorder(self, n, connections):
        from collections import defaultdict, deque

        # Build graph: store direction by sign (u->v is positive, v->u is negative)
        graph = defaultdict(list)
        for u, v in connections:
            graph[u].append((v, 1))   # original direction u -> v
            graph[v].append((u, 0))   # reverse direction v -> u

        visited = set()
        queue = deque([0])
        visited.add(0)
        changes = 0

        while queue:
            node = queue.popleft()
            for neighbor, needs_change in graph[node]:
                if neighbor not in visited:
                    changes += needs_change
                    visited.add(neighbor)
                    queue.append(neighbor)
        return changes
      

class Solution {
public:
    int minReorder(int n, vector<vector<int>>& connections) {
        vector<vector<pair<int,bool>>> graph(n);
        for (auto& conn : connections) {
            graph[conn[0]].push_back({conn[1], true});  // original direction
            graph[conn[1]].push_back({conn[0], false}); // reverse direction
        }
        vector<bool> visited(n, false);
        queue<int> q;
        q.push(0);
        visited[0] = true;
        int changes = 0;
        while (!q.empty()) {
            int node = q.front(); q.pop();
            for (auto& [neighbor, needsChange] : graph[node]) {
                if (!visited[neighbor]) {
                    changes += needsChange;
                    visited[neighbor] = true;
                    q.push(neighbor);
                }
            }
        }
        return changes;
    }
};
      

class Solution {
    public int minReorder(int n, List<List<Integer>> connections) {
        List<List<int[]>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
        for (List<Integer> conn : connections) {
            int u = conn.get(0), v = conn.get(1);
            graph.get(u).add(new int[]{v, 1}); // original direction
            graph.get(v).add(new int[]{u, 0}); // reverse direction
        }
        boolean[] visited = new boolean[n];
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(0);
        visited[0] = true;
        int changes = 0;
        while (!queue.isEmpty()) {
            int node = queue.poll();
            for (int[] edge : graph.get(node)) {
                int neighbor = edge[0], needsChange = edge[1];
                if (!visited[neighbor]) {
                    changes += needsChange;
                    visited[neighbor] = true;
                    queue.offer(neighbor);
                }
            }
        }
        return changes;
    }
}
      

var minReorder = function(n, connections) {
    const graph = Array.from({length: n}, () => []);
    for (const [u, v] of connections) {
        graph[u].push([v, 1]); // original direction
        graph[v].push([u, 0]); // reverse direction
    }
    const visited = new Array(n).fill(false);
    let changes = 0;
    const queue = [0];
    visited[0] = true;

    while (queue.length) {
        const node = queue.shift();
        for (const [neighbor, needsChange] of graph[node]) {
            if (!visited[neighbor]) {
                changes += needsChange;
                visited[neighbor] = true;
                queue.push(neighbor);
            }
        }
    }
    return changes;
};
      

Problem Description

Given n cities numbered from 0 to n-1 and a list of connections where each connection is a directed road [a, b] from city a to city b, you are to reorient some of these roads so that all cities can reach city 0 via a path following the direction of the roads.

Your task is to find the minimum number of roads that need to be changed in direction so that, for every city, there exists a path following the direction of the roads that leads to city 0.

Constraints:

• There are n-1 connections, so the network is a tree (connected, no cycles).
• Each connection is a one-way road.
• Only change the direction of roads, do not create or remove roads.
• Do not reuse elements or change their endpoints; only reverse the direction if needed.
• One valid solution is guaranteed to exist.

Thought Process

At first glance, the brute-force approach would be to try all combinations of road direction changes and check if every city can reach city 0. However, this would be highly inefficient, especially for larger values of n.

Instead, let's rethink the problem: since the network forms a tree, there is exactly one unique path from every city to city 0. The only thing that can prevent a city from reaching 0 is if one or more roads along its unique path are pointing away from 0.

So, if we can traverse the tree starting from city 0 and count how many roads are "pointing the wrong way" (i.e., away from 0), we can determine the minimum number of changes needed. This leads us to a traversal-based solution.

Solution Approach

We can use either BFS or DFS starting from city 0 to traverse the tree. The key idea is to represent the graph in such a way that, for each edge, we can quickly determine if it needs to be reversed.

• Step 1: Build an adjacency list for the graph. For each connection [a, b], add (b, 1) to a's list (indicating the original direction) and (a, 0) to b's list (indicating the reverse direction).
• Step 2: Start a BFS or DFS from city 0. For each neighboring city, check the direction:
  • If the direction is from the current city to the neighbor (i.e., away from 0), increment the change counter because we need to reverse this road.
  • If the direction is towards the current city (i.e., towards 0), no change is needed.
• Step 3: Mark each visited city to avoid cycles (though the tree has none, this prevents redundant work).
• Step 4: Continue until all cities are visited. The accumulated count gives the minimum number of roads to reverse.

We use a hash map (or array of lists) for fast lookups, and a queue or stack for traversal. The overall process is efficient and leverages the tree structure.

Example Walkthrough

Let's consider n = 6 and connections = [[0,1],[1,3],[2,3],[4,0],[4,5]].

• Step 1: Build the graph. For each connection, store both the original and reverse directions:
  • 0: (1, 1), (4, 0)
  • 1: (0, 0), (3, 1)
  • 2: (3, 1)
  • 3: (1, 0), (2, 0)
  • 4: (0, 1), (5, 1)
  • 5: (4, 0)
• Step 2: Start BFS from node 0:
  • Visit 1: direction is (1, 1) from 0 to 1 (away from 0), so increment changes to 1.
  • Visit 4: direction is (4, 0) from 0 to 4 (towards 0), so no change needed.
• Step 3: Visit children of 1:
  • 0 is already visited.
  • 3: direction is (3, 1) from 1 to 3 (away from 0), increment changes to 2.
• Step 4: Visit children of 4:
  • 0 is already visited.
  • 5: direction is (5, 1) from 4 to 5 (away from 0), increment changes to 3.
• Step 5: Visit children of 3:
  • 1 is already visited.
  • 2: direction is (2, 0) from 3 to 2 (towards 0), no change needed.
• Step 6: Visit children of 5 and 2: all already visited.

Final answer: 3 roads must be reversed.

Time and Space Complexity

Brute-force approach: Trying all combinations of road reversals is exponential in the number of connections, i.e., O(2^n-1), and is not feasible.

Optimized approach:

• Time Complexity: O(n), because we visit each node and edge exactly once during the traversal.
• Space Complexity: O(n), for the adjacency list and visited set/array.

Summary

The key insight is that the problem reduces to counting the number of roads that point away from city 0 on the unique path from each city to 0. By traversing the tree starting at 0 and counting such roads, we efficiently compute the minimum number of changes required. The solution leverages properties of trees and adjacency lists, resulting in an elegant and optimal O(n) approach.