#1466 - Reorder Routes to Make All Paths Lead to the City Zero

MediumGraphs - DFS

There are n cities numbered 0 to n - 1 and n - 1 directed roads forming a tree. Reorder the minimum number of roads so that every city can reach city 0. Return the minimum number of edges that need to be reversed.

Input	Output
n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]	3
n = 5, connections = [[1,0],[1,2],[3,2],[3,4]]	2
n = 3, connections = [[1,0],[2,0]]	0

Solution Space

Try it

/**
 * Returns the minimum number of edges to reverse so every city can reach city 0.
 * Builds an undirected adjacency list, tagging each edge as original or reversed.
 * DFS from 0; every edge traversed in its original direction (away from 0) must be flipped.
 *
 * @param n           Number of cities
 * @param connections Directed edges [from, to]
 * @returns           Minimum reversals
 */
export function minReorder(n: number, connections: number[][]): number {
  // Build adjacency list: [neighbor, needsReversal]
  const graph: [number, boolean][][] = Array.from({ length: n }, () => []);

  for (const [a, b] of connections) {
    graph[a].push([b, true]); // original direction (a→b) needs reversal if traversed
    graph[b].push([a, false]); // reverse direction is free
  }

  const visited = new Array<boolean>(n).fill(false);
  let reversals = 0;

  function dfs(city: number): void {
    visited[city] = true;
    for (const [neighbor, isOriginal] of graph[city]) {
      if (!visited[neighbor]) {
        if (isOriginal) reversals++; // edge points away from 0 → must reverse
        dfs(neighbor);
      }
    }
  }

  dfs(0);
  return reversals;
}

Approach: DFS from city 0 on an augmented undirected graph – tag each edge as "original" or "reverse." Edges traversed in their original direction (away from 0) need to be flipped.

Time: O(n) – tree has n − 1 edges, each visited once.

Space: O(n) – adjacency list and visited array.

#841 Keys and Rooms

#200 Number of Islands