1466. Reorder Routes to Make All Paths Lead to the City Zero
Tags:
Medium
Skills:
Graph
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bài toán yêu cầu xác định số lượng tối thiểu các cạnh cần được đổi chiều để đảm bảo tất cả các thành phố có thể đi đến thành phố 0. Đây là một bài toán về đồ thị, nơi mỗi thành phố là một đỉnh và mỗi con đường là một cạnh có hướng
Approach
Time and space complexity
Solution
1function minReorder(n: number, connections: number[][]): number {
2 let graph: Map<number, [number, boolean][]> = new Map();
3
4 for (const [from, to] of connections) {
5 if (!graph.has(from)) graph.set(from, [])
6 if (!graph.has(to)) graph.set(to, [])
7 graph.get(from).push([to, true])
8 graph.get(to).push([from, false])
9 }
10
11 let visisted: boolean[] = Array(n).fill(false);
12
13 function dfs(node: number): number {
14 visisted[node] = true;
15 let re_order_count = 0;
16
17 const neighbors = graph.get(node);
18 for (const [neighbor, original_direction] of neighbors) {
19 if (!visisted[neighbor]) {
20 if (original_direction) {
21 re_order_count++
22 }
23
24 re_order_count += dfs(neighbor)
25 }
26 }
27
28 return re_order_count
29 }
30
31 return dfs(0)
32};