[閒聊] 每日leetcode 75 - Day24 - 3

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 } } --
※ 批踢踢實業坊(ptt.cc), 來自: 60.248.143.172 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1751881679.A.6F6.html