作者yam276 (史萊哲林的優等生)
標題[閒聊] 每日leetcode 75 - Day25
時間2025-07-08 18:13:03
1466. Reorder Routes to Make All Paths Lead to the City Zero
題目:
給你一個有向圖
反轉幾次路徑方向可以讓大家都能到首都
思路:
建立一個鄰接表
讓他儲存 a->b 以及 b->a 兩條路徑
之後雖然這題目沒有圖循環
但還是養成檢查 visited: &mut Vec<bool> 的好習慣
接著開始 dfs 從首都開始
因為儲存的時候我們是存 a->b
所以我們發現路線是 a->b 即 cur->nearby 的時候
才是需要反轉路徑的情況 於是 count+=1 反之就不管
第二層的時候代表 0->1 已經被處理過
所以處理 1->2 就同時代表 0->2
Code:
impl Solution {
pub fn min_reorder(n: i32, connections: Vec<Vec<i32>>) -> i32 {
fn dfs(
cur: usize,
graph: &Vec<Vec<(usize, bool)>>,
visited: &mut Vec<bool>,
count: &mut i32,
) {
visited[cur] = true;
for &(nearby_city, need_reverse) in &graph[cur] {
if !visited[nearby_city] {
if need_reverse {
*count += 1;
}
dfs(nearby_city, graph, visited, count);
}
}
}
let mut graph = vec![vec![]; n as usize];
for conn in connections {
let a = conn[0] as usize;
let b = conn[1] as usize;
graph[a].push((b, true));
graph[b].push((a, false));
}
let mut visited = vec![false; n as usize];
let mut count = 0;
dfs(0, &graph, &mut visited, &mut count);
count
}
}
--
※ 發信站: 批踢踢實業坊(web-ptt.org.tw), 來自: 60.248.143.172 (臺灣)
※ 文章網址: https://web-ptt.org.tw/Marginalman/M.1751969585.A.28A