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