# Reorder Routes to Make All Paths Lead to the City Zero
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/reorder-routes-to-make-all-paths-lead-to-the-city-zero)
Canonical: https://scaleengineer.com/dsa/problems/reorder-routes-to-make-all-paths-lead-to-the-city-zero
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Graph
**Companies:** [Docusign](https://scaleengineer.com/companies/docusign), [DRW](https://scaleengineer.com/companies/drw)
---
## 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] = [ai, bi]` represents a road from city `ai` to city `bi`.

This year, there will be a big event in the capital (city `0`), and many people want to travel to this city.

Your task consists of reorienting some roads such that each city can visit the city `0`. Return the **minimum** number of edges changed.

It's **guaranteed** that each city can reach city `0` after reorder.

**Example 1:**

![](https://assets.glich.co/dsa/reorder-routes-to-make-all-paths-lead-to-the-city-zero/image0.png) 

**Input:** n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]
**Output:** 3
**Explanation:** Change the direction of edges show in red such that each node can reach the node 0 (capital).

**Example 2:**

![](https://assets.glich.co/dsa/reorder-routes-to-make-all-paths-lead-to-the-city-zero/image1.png) 

**Input:** n = 5, connections = [[1,0],[1,2],[3,2],[3,4]]
**Output:** 2
**Explanation:** Change the direction of edges show in red such that each node can reach the node 0 (capital).

**Example 3:**

**Input:** n = 3, connections = [[1,0],[2,0]]
**Output:** 0

**Constraints:**

* `2 <= n <= 5 * 104`
* `connections.length == n - 1`
* `connections[i].length == 2`
* `0 <= ai, bi <= n - 1`
* `ai != bi`

# Approaches
## Path-based Checking for Each City
This approach iterates through every city (from 1 to n-1). For each city, it finds the unique path to the capital (city 0) and checks the orientation of each edge along this path. If an edge is pointing away from the capital, it's counted as a required reorientation. A set is used to keep track of already reoriented edges to avoid double counting.
**Time:** O(N^2). The outer loop runs N-1 times. Inside the loop, the BFS to find a path takes O(N+M) = O(N) time since M=N-1. This results in a total time complexity of O(N*N). · **Space:** O(N^2) in the worst case. The queue for BFS can store paths, and the total length of all paths can be quadratic in a star-like graph. The adjacency list and other sets take O(N) space.
**Pros:** Conceptually straightforward, as it directly models the problem requirement for each city.
**Cons:** Extremely inefficient with a time complexity of O(N^2), which will lead to a 'Time Limit Exceeded' error on larger test cases.; The implementation is complex, requiring pathfinding and reconstruction for each node.; Performs a lot of redundant computations by repeatedly traversing the same edges for different starting cities.
### Explanation
The fundamental idea is to ensure that for every city, its path to the capital (city 0) consists of correctly oriented roads. We can tackle this by examining each city one by one.

For each city `i` (where `i > 0`), we find the single path that connects it to city 0 in the underlying tree structure. This can be done using a graph traversal algorithm like Breadth-First Search (BFS) or Depth-First Search (DFS). Once we have the path, say `i -> p1 -> p2 -> ... -> 0`, we check each segment. For a segment `u -> v` (where `v` is closer to 0), the road must be directed from `u` to `v`. If the original road was `v -> u`, it's pointing the wrong way and must be flipped.

To avoid counting the same flip multiple times (as edges are part of multiple paths), we use a `Set` to store the unique edges that require reorientation. The final answer is the size of this set.

This method is correct but highly inefficient because finding the path from each of the `N-1` cities to the root takes approximately `O(N)` time, leading to an overall quadratic time complexity.

```java
import java.util.*;

class Solution {
    public int minReorder(int n, int[][] connections) {
        // Build undirected graph
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        // Store original directions for O(1) lookup
        Set<String> roads = new HashSet<>();
        for (int[] conn : connections) {
            adj.get(conn[0]).add(conn[1]);
            adj.get(conn[1]).add(conn[0]);
            roads.add(conn[0] + "," + conn[1]);
        }

        Set<String> edgesToFlip = new HashSet<>();

        // For each city, find path to 0 and check edges
        for (int i = 1; i < n; i++) {
            // Find path from i to 0 using BFS
            Queue<List<Integer>> queue = new LinkedList<>();
            queue.add(Arrays.asList(i));
            boolean[] visited = new boolean[n];
            visited[i] = true;

            while (!queue.isEmpty()) {
                List<Integer> path = queue.poll();
                int u = path.get(path.size() - 1);

                if (u == 0) {
                    // Path found, check its edges
                    for (int k = 0; k < path.size() - 1; k++) {
                        int from = path.get(k);
                        int to = path.get(k + 1);
                        // Path needs edge from->to. If original is not from->to, it must be flipped.
                        if (!roads.contains(from + "," + to)) {
                            edgesToFlip.add(to + "," + from);
                        }
                    }
                    break; // Move to next city
                }

                for (int v : adj.get(u)) {
                    if (!visited[v]) {
                        visited[v] = true;
                        List<Integer> newPath = new ArrayList<>(path);
                        newPath.add(v);
                        queue.add(newPath);
                    }
                }
            }
        }
        return edgesToFlip.size();
    }
}
```
### Algorithm
- Build an undirected graph representation using an adjacency list.
- Store the original directed roads in a `Set` for quick lookups.
- Initialize a `Set` to store the unique edges that need to be flipped.
- Loop through each city `i` from `1` to `n-1`.
- Inside the loop, perform a Breadth-First Search (BFS) starting from city `i` to find the unique path to city `0`.
- During the BFS, keep track of the path taken to reach each node.
- Once city `0` is reached, reconstruct the path from `i` to `0`.
- Iterate over the edges `(u, v)` in this path, where `u` is farther from `0` and `v` is closer.
- For each edge, check if the original road was `u -> v`. If not (meaning it was `v -> u`), add it to the set of edges to flip.
- Finally, the size of the set gives the minimum number of reorientations.

## Single Graph Traversal from Capital (DFS/BFS)
This optimal approach involves a single traversal of the graph, starting from the capital (city 0). We can use either Depth-First Search (DFS) or Breadth-First Search (BFS). As we traverse away from the capital, we check the direction of each road. If a road is directed away from the capital (i.e., from an already visited node to a new node), it must be reoriented.
**Time:** O(N). Both DFS and BFS visit each node and edge exactly once. Since the graph is a tree, it has N nodes and N-1 edges. The complexity is O(N + M) = O(N). · **Space:** O(N). The adjacency list requires O(N + M) = O(N) space as M=N-1. The recursion stack for DFS or the queue for BFS can also take up to O(N) space in the worst case (for a skewed tree).
**Pros:** Optimal time and space complexity.; Solves the problem in a single pass over the graph.; The logic is clean and avoids redundant calculations.
**Cons:** Requires a slightly more complex graph representation to store edge directions along with connectivity.
### Explanation
A more efficient way to solve this problem is to change our perspective. Instead of checking paths from all cities *to* city 0, we can start a single traversal *from* city 0 and explore the entire network. We can think of the graph as a tree rooted at city 0. For every city to be able to reach city 0, every edge in this tree must be directed towards the root (city 0).

We can use a Depth-First Search (DFS) or Breadth-First Search (BFS) for the traversal. Let's start at city 0. When we traverse from a node `u` to a neighbor `v`, `u` is closer to the root `0` than `v`. Therefore, the road between them must be oriented as `v -> u`.

If the original road was `u -> v`, it's pointing away from the capital and needs to be reoriented. We increment a counter for each such case. If the road was already `v -> u`, it's correctly oriented, and we do nothing.

To implement this, we build an adjacency list where for each original road `u -> v`, we add two entries: one for `u` pointing to `v` (marking it as an original-direction edge) and one for `v` pointing to `u` (marking it as a reverse-direction edge). During the traversal from the root, whenever we cross an original-direction edge, we count it as a necessary reorientation.

### DFS Implementation
```java
import java.util.*;

class Solution {
    int reorientations = 0;

    public int minReorder(int n, int[][] connections) {
        List<List<int[]>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }

        for (int[] conn : connections) {
            // conn[0] -> conn[1]
            // Add edge from conn[0] to conn[1], direction 1 (original)
            adj.get(conn[0]).add(new int[]{conn[1], 1});
            // Add edge from conn[1] to conn[0], direction 0 (artificial for traversal)
            adj.get(conn[1]).add(new int[]{conn[0], 0});
        }

        dfs(0, -1, adj);
        return reorientations;
    }

    private void dfs(int u, int parent, List<List<int[]>> adj) {
        for (int[] edge : adj.get(u)) {
            int v = edge[0];
            int direction = edge[1];

            if (v == parent) {
                continue;
            }

            // If direction is 1, it's an edge u -> v.
            // Since we traverse from 0 outwards, u is closer to 0 than v.
            // This edge points away from the capital and needs to be flipped.
            if (direction == 1) {
                reorientations++;
            }
            
            dfs(v, u, adj);
        }
    }
}
```

### BFS Implementation
```java
import java.util.*;

class Solution {
    public int minReorder(int n, int[][] connections) {
        List<List<int[]>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }

        for (int[] conn : connections) {
            adj.get(conn[0]).add(new int[]{conn[1], 1}); // 1 means original direction
            adj.get(conn[1]).add(new int[]{conn[0], 0}); // 0 means reverse direction
        }

        int reorientations = 0;
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(0);
        boolean[] visited = new boolean[n];
        visited[0] = true;

        while (!queue.isEmpty()) {
            int u = queue.poll();
            for (int[] edge : adj.get(u)) {
                int v = edge[0];
                if (visited[v]) {
                    continue;
                }
                visited[v] = true;
                // If we traverse u -> v and the original edge was u -> v (direction=1),
                // it needs to be flipped.
                if (edge[1] == 1) {
                    reorientations++;
                }
                queue.offer(v);
            }
        }
        return reorientations;
    }
}
```
### Algorithm
- Reframe the problem: Instead of checking paths to city 0, we can start from city 0 and traverse outwards. Any road pointing away from city 0 must be reoriented.
- Build an adjacency list that stores not only the neighbors but also the direction of the original road. For a connection `u -> v`, we can store `(v, 1)` in `u`'s list and `(u, 0)` in `v`'s list, where `1` indicates an original direction and `0` indicates an artificial/reverse edge for traversal.
- Start a traversal (DFS or BFS) from city 0.
- Maintain a count of reorientations, initialized to 0.
- During the traversal, when moving from a visited node `u` to an unvisited node `v`:
  - Check the direction of the edge between `u` and `v`.
  - If the edge was originally `u -> v` (indicated by the direction flag `1`), it means the road is pointing away from the capital. This road must be flipped, so we increment the count.
  - If the edge was `v -> u` (direction flag `0`), it's already pointing towards the capital, so no change is needed.
- Continue the traversal until all cities are visited. The final count is the minimum number of reorientations.

# Solutions
### Java

```java
class Solution {
private
  List<int[]>[] g;
public
  int minReorder(int n, int[][] connections) {
    g = new List[n];
    Arrays.setAll(g, k->new ArrayList<>());
    for (var e : connections) {
      int a = e[0], b = e[1];
      g[a].add(new int[]{b, 1});
      g[b].add(new int[]{a, 0});
    }
    return dfs(0, -1);
  }
private
  int dfs(int a, int fa) {
    int ans = 0;
    for (var e : g[a]) {
      int b = e[0], c = e[1];
      if (b != fa) {
        ans += c + dfs(b, a);
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minReorder(int n, vector<vector<int>> &connections) {
    vector<pair<int, int>> g[n];
    for (auto &e : connections) {
      int a = e[0], b = e[1];
      g[a].emplace_back(b, 1);
      g[b].emplace_back(a, 0);
    }
    function<int(int, int)> dfs = [&](int a, int fa) {
      int ans = 0;
      for (auto &[b, c] : g[a]) {
        if (b != fa) {
          ans += c + dfs(b, a);
        }
      }
      return ans;
    };
    return dfs(0, -1);
  }
};

```

### Python

```python
class Solution:
    def minReorder(self, n: int, connections: List[List[int]]) -> int: def dfs(a: int, fa: int) -> int: return sum(c + dfs(b, a) for b, c in g[a] if b != fa) g = [[] for _ in range(n)] for a, b in connections: g[a]. append((b, 1)) g[b]. append((a, 0)) return dfs(0, - 1)

```