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
}
}