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]
= [
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:
n
<= 5 * 104connections.length
== n
- 1connections[i].length
== 2n
- 1
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
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