Reorient the Fewest Roads Toward the Capital

medium graph dfs

Problem

You are given n − 1 directed roads forming a tree on cities 0..n−1. Return the minimum number of roads to flip so every city can reach city 0. Build an undirected adjacency map that remembers each edge's original direction; DFS from 0 and increment the counter whenever an edge originally pointed away from 0.

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_;
}

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