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