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

題目描述

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⁴
• 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

Ron ChenFri, 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％ㄌ，好ㄟ 又學習ㄌgpwork4uFri, 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去做比對…感覺特別傻
MarsgoatFri, 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%
MarsgoatMar 25, 2023

Reference

回到題目列表