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

• Time: $O(n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 class Solution { public: int minReorder(int n, vector>& connections) { vector> graph(n); for (const vector& conn : connections) { graph[conn[0]].push_back(conn[1]); graph[conn[1]].push_back(-conn[0]); // - := conn[0] -> conn[1] } return dfs(graph, 0, -1); } private: int dfs(const vector>& graph, int u, int parent) { int change = 0; for (const int v : graph[u]) { if (abs(v) == parent) continue; if (v > 0) ++change; change += dfs(graph, abs(v), u); } return change; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 class Solution { public int minReorder(int n, int[][] connections) { List[] graph = new List[n]; for (int i = 0; i < n; ++i) graph[i] = new ArrayList<>(); for (int[] conn : connections) { graph[conn[0]].add(conn[1]); graph[conn[1]].add(-conn[0]); // - := conn[0] -> conn[1] } return dfs(graph, 0, -1); } private int dfs(List[] graph, int u, int parent) { int change = 0; for (final int v : graph[u]) { if (Math.abs(v) == parent) continue; if (v > 0) ++change; change += dfs(graph, Math.abs(v), u); } return change; } }