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

###### tags: `Medium`,`DFS`,`BFS`,`Graph`

[1466. Reorder Routes to Make All Paths Lead to the City Zero](https://leetcode.com/problems/reorder-routes-to-make-all-paths-lead-to-the-city-zero/)

### 題目描述

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]` = [$a_i$, $b_i$] represents a road from city $a_i$ to city $b_i$.

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:**


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:**


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 * 10^4^
* `connections.length` == `n` - 1
* `connections[i].length` == 2
* 0 <= $a_i$, $b_i$ <= `n` - 1
* $a_i$ != $b_i$

### 解答
#### Python

class Solution:
    def minReorder(self, n: int, connections: List[List[int]]) -> int:
        graph = defaultdict(dict)
        self.ans = 0

        # forward = 1, backward = 0
        for u, v in connections:
            graph[u][v] = 1
            graph[v][u] = 0

        visisted = set()

        def dfs(node):
            visisted.add(node)
            for nei, direct in graph[node].items():
                if nei not in visisted:
                    self.ans += direct
                    dfs(nei)

        dfs(0)
        return self.ans

> [name=Ron Chen][time=Fri, Mar 24, 2023]

class Solution:
    def minReorder(self, n: int, connections: List[List[int]]) -> int:
        graph = {
            i:{} for i in range(n)
        }

        for conn in connections:
            graph[conn[0]][conn[1]] = 1
            graph[conn[1]][conn[0]] = 0

        is_visited = set()
        is_visited.add(0)
        visit_nodes = [0]
        count = 0
        while len(visit_nodes) > 0:
            next_visit_nodes = []
            for node in visit_nodes:
                for i, direct in graph[node].items():
                    if i in is_visited:
                        continue
                    is_visited.add(i)
                    next_visit_nodes.append(i)
                    if direct:
                        count += 1
            visit_nodes = next_visit_nodes
        return count

> 看 Ron 神ㄉ改ㄌ一下資料結構從 Beat 18% 變成 76％ㄌ，好ㄟ 又學習ㄌ[name=gpwork4u][time=Fri, Mar 24, 2023]

#### Javascript

function minReorder(n, connections) {
  const graph = new Array(n).fill(0).map(() => []);
  const graph2 = new Array(n).fill(0).map(() => []);
  for (const [v1, v2] of connections) {
    graph[v1].push(v2);
    graph[v2].push(v1);
    graph2[v1].push(v2);
  }

  const visited = new Array(n).fill(false);
  let count = 0;

  const stack = [0];
  while (stack.length) {
    const node = stack.pop();
    if (visited[node]) continue;
    visited[node] = true;
    for (const vertex of graph[node]) {
      if (visited[vertex]) continue;
      if (graph2[node].includes(vertex)) {
        count++;
      }
      stack.push(vertex);
    }
  }

  return count;
}

> 想半天最後建兩種graph去做比對...感覺特別傻
> [name=Marsgoat][time=Fri, Mar 24, 2023]

function minReorder(n, connections) {
  const graph = new Array(n).fill(0).map(() => []);
  for (const [v1, v2] of connections) {
    graph[v1].push(v2);
    graph[v2].push(-v1);
  }

  const visited = new Array(n).fill(false);
  let count = 0;

  const stack = [0];
  while (stack.length) {
    const node = stack.pop();
    if (visited[node]) continue;
    visited[node] = true;
    for (const vertex of graph[node]) {
      if (visited[Math.abs(vertex)]) continue;
      if (vertex > 0) {
        count++;
      }

      stack.push(Math.abs(vertex));
    }
  }

  return count;
}

> 分享一下除了樓上兩位大神的解法，看到的另一種做法，感覺也不錯，beat94%
> [name=Marsgoat][time=Mar 25, 2023]

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)