1466. Reorder Routes to Make All Paths Lead to the City Zero
DFS, BFS, Graph, AMateList ·Problem Statement
link: LeetCode.cn LeetCode 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:
Input: n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]
Output: 3
Input: n = 5, connections = [[1,0],[1,2],[3,2],[3,4]]
Output: 2
Input: n = 3, connections = [[1,0],[2,0]]
Output: 0
Solution Approach
To reorder routes so all paths lead to city zero, traverse the graph using DFS or BFS, counting and reversing directed edges that lead away from the root, ensuring all cities can reach city zero.
Algorithm
- Graph Representation: Represent the graph using adjacency lists, where each connection is stored with a direction indicator (1 for an edge pointing away from city 0, and 0 for an edge pointing towards city 0).
- Traversal Method: Use Depth-First Search (DFS) or Breadth-First Search (BFS) to traverse the graph starting from city 0, ensuring all cities can reach city 0.
- Edge Reordering: During traversal, count the number of directed edges that need to be reversed to ensure all cities can access city 0, and sum these to get the minimum number of changes required.
Implement
class Solution:
def minReorder(self, n: int, connections: List[List[int]]) -> int:
edge = defaultdict(list)
for x, y in connections:
edge[x].append((y, 1))
edge[y].append((x, 0))
res = 0
s = [(0, -1)]
while s:
cur, parent = s.pop()
for node, direction in edge[cur]:
if node != parent:
res += direction
s.append((node, cur))
return res
//java code
import java.util.HashMap;
import java.util.Map;
class Solution {
public int minReorder(int n, int[][] connections) {
// List<int[]>[] e = new List[n];
// for (int i = 0; i < n; i++) {
// e[i] = new ArrayList<int[]>();
// }
// for (int[]edge: connections) {
// e[edge[0]].add(new int[]{edge[1], 1});
// e[edge[1]].add(new int[]{edge[0], 0});
// }
// printEdges(e);
// return dfs(0, -1, e);
// }
// public int dfs(int x, int parent, List<int[]>[] e) {
// int res = 0;
// for (int[] edge: e[x]) {
// if (edge[0] == parent) {
// continue;
// }
// res += edge[1] + dfs(edge[0], x, e);
// }
// return res;
// }
// private void printEdges(List<int[]>[] e) {
// for (int i = 0; i < e.length; i++) {
// System.out.print("Node " + i + ": ");
// for (int[] edge : e[i]) {
// System.out.print(Arrays.toString(edge) + " ");
// }
// System.out.println();
// }
// }
List<int[]>[] edge = new ArrayList[n];
for (int i = 0; i < n; i++) {
edge[i] = new ArrayList<>();
}
for (int[] connection : connections) {
edge[connection[0]].add(new int[]{connection[1], 1});
edge[connection[1]].add(new int[]{connection[0], 0});
}
int res = 0;
Stack<int[]> stack = new Stack<>();
stack.push(new int[]{0, -1});
while (!stack.isEmpty()) {
int[] current = stack.pop();
int cur = current[0];
int parent = current[1];
for (int[] next : edge[cur]) {
int node = next[0];
int direction = next[1];
if (node != parent) {
res += direction;
stack.push(new int[]{node, cur});
}
}
}
return res;
}
}