547. Number of Provinces
题目：
一个国家有很多省
一个省有很多城市
只有同省的城市互相连通
求总共几个省
思路：
写一个 dfs function
每次探测都会探索有能去的地方并标记来过
主程式会扫描没来过城市 并使用 dfs function
每次启动 dfs 代表找到新省分
因为同省的会在 dfs 里面被标记
Code:
impl Solution {
pub fn find_circle_num(is_connected: Vec<Vec<i32>>) -> i32 {
fn dfs(room: usize,
is_connected: &Vec<Vec<i32>>,
visited: &mut Vec<bool>) {
visited[room] = true;
for near_room in 0..is_connected.len() {
if is_connected[room][near_room] == 1 && !visited[near_room] {
dfs(near_room, is_connected, visited);
}
}
}
let n = is_connected.len();
let mut visited = vec![false; n];
let mut area = 0;
for i in 0..n {
if !visited[i] {
dfs(i, &is_connected, &mut visited);
area += 1;
}
}
area
}
}