Skip to content

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<vector<int>>& connections) {
    vector<vector<int>> graph(n);

    for (const vector<int>& 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<vector<int>>& 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<Integer>[] 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<Integer>[] 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;
  }
}