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
29
30
class Solution {
 public:
  int minReorder(int n, vector<vector<int>>& connections) {
    vector<vector<int>> graph(n);

    for (const vector<int>& connection : connections) {
      const int u = connection[0];
      const int v = connection[1];
      graph[u].push_back(v);
      graph[v].push_back(-u);  // - := u -> v
    }

    return dfs(graph, 0, -1);
  }

 private:
  int dfs(const vector<vector<int>>& graph, int u, int prev) {
    int change = 0;

    for (const int v : graph[u]) {
      if (abs(v) == prev)
        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
30
31
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[] connection : connections) {
      final int u = connection[0];
      final int v = connection[1];
      graph[u].add(v);
      graph[v].add(-u); // - := u -> v
    }

    return dfs(graph, 0, -1);
  }

  private int dfs(List<Integer>[] graph, int u, int prev) {
    int change = 0;

    for (final int v : graph[u]) {
      if (Math.abs(v) == prev)
        continue;
      if (v > 0)
        ++change;
      change += dfs(graph, Math.abs(v), u);
    }

    return change;
  }
}