Reorder Routes to Make All Paths Lead to the City Zero

medium graph dfs

Problem

There are n cities numbered from 0 to n-1 and n-1 roads such that there is only one way to travel between two different cities (this network form a tree). Last year, The ministry of transport decided to orient the roads in one direction because they are too narrow. Roads are represented by connections where connections[i] = [a, b] represents a road from city a to b.

Inputn = 6, edges = [[0,1],[1,3],[2,3],[4,0],[4,5]]

Output3

Edges originally pointing away from city 0 must be flipped.

edges (e.g. "0,1; 1,3; 2,3; 4,0; 4,5")

def min_reorder(n, edges):
    adj = [[] for _ in range(n)]
    for a, b in edges:
        adj[a].append((b, 1))
        adj[b].append((a, 0))
    count = 0
    seen = [False] * n; seen[0] = True
    def dfs(u):
        nonlocal count
        for v, c in adj[u]:
            if not seen[v]:
                seen[v] = True; count += c; dfs(v)
    dfs(0)
    return count

function minReorder(n, edges) {
  const adj = Array.from({ length: n }, () => []);
  for (const [a, b] of edges) {
    adj[a].push([b, 1]); // outgoing — needs flip if traversed
    adj[b].push([a, 0]);
  }
  let count = 0;
  const seen = new Array(n).fill(false); seen[0] = true;
  function dfs(u) { for (const [v, c] of adj[u]) if (!seen[v]) { seen[v] = true; count += c; dfs(v); } }
  dfs(0);
  return count;
}

class Solution {
    int count;
    boolean[] seen;
    List<int[]>[] adj;
    public int minReorder(int n, int[][] edges) {
        adj = new List[n];
        for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
        for (int[] e : edges) {
            adj[e[0]].add(new int[]{ e[1], 1 });
            adj[e[1]].add(new int[]{ e[0], 0 });
        }
        count = 0;
        seen = new boolean[n]; seen[0] = true;
        dfs(0);
        return count;
    }
    private void dfs(int u) {
        for (int[] e : adj[u]) if (!seen[e[0]]) { seen[e[0]] = true; count += e[1]; dfs(e[0]); }
    }
}

int count_;
vector<bool> seen_;
vector<vector<pair<int,int>>> adj_;
void dfs(int u) {
    for (auto& [v, c] : adj_[u]) if (!seen_[v]) { seen_[v] = true; count_ += c; dfs(v); }
}
int minReorder(int n, vector<vector<int>>& edges) {
    adj_.assign(n, {});
    for (auto& e : edges) {
        adj_[e[0]].push_back({e[1], 1});
        adj_[e[1]].push_back({e[0], 0});
    }
    count_ = 0;
    seen_.assign(n, false); seen_[0] = true;
    dfs(0);
    return count_;
}

Explanation

The roads form a tree, so ignoring direction there is exactly one path between city 0 and every other city. We want every city to be able to reach 0, which means along each of those paths the edges should point toward 0. The answer is simply the count of edges that currently point the wrong way.

The trick is to build the graph as undirected but tag each edge with its original direction. When we add real edge a → b, we store (b, 1) in a's list (cost 1 if we walk it, because it points away from 0) and (a, 0) in b's list (the reverse, cost 0).

Now we run a DFS starting at city 0. As we move outward from 0 to a neighbor, walking an edge with tag 1 means that edge was pointing away from 0, so it must be flipped — we add its cost to count. Tag 0 edges already point toward 0, so they cost nothing.

Example: edges = [[0,1],[1,3],[2,3],[4,0],[4,5]]. Walking outward from 0, the edges 0→1, 1→3, 4→5 happen to point away from 0 along the traversal and need flipping, giving 3.

Because it's a tree, the DFS touches every edge exactly once, so a single pass gives the total number of flips.

Time: O(n) Space: O(n)