[−][src]Function leetcode_for_rust::cd0547_friend_circles::find_circle_num
pub fn find_circle_num(m: Vec<Vec<i32>>) -> i32
Solutions
Approach 1: Union Find
-
Time complexity: O(m*n)
-
Space complexity: O(m*n)
-
Runtime: 0 ms
-
Memory: 2.7 MB
struct UnionFind { parents: Vec<i32>, count: i32, } impl UnionFind { fn new(grid: &Vec<Vec<i32>>) -> Self { let m = grid.len(); let count = m as i32; let mut parents = vec![]; for i in 0..m { parents.push(i as i32); } UnionFind { parents: parents, count: count } } fn find(&mut self, i: i32) -> i32 { if self.parents[i as usize] != i { self.parents[i as usize] = self.find(self.parents[i as usize]) }; self.parents[i as usize] } fn union(&mut self, x: i32, y: i32) -> i32 { let x_parent = self.find(x); let y_parent = self.find(y); if x_parent == y_parent { return self.count; } self.parents[x_parent as usize] = y_parent; self.count -= 1; self.count } } impl Solution { pub fn find_circle_num(m: Vec<Vec<i32>>) -> i32 { if m.is_empty() { return 0; } let n = m.len(); let mut uf = UnionFind::new(&m); for i in 0..n { for j in 0..n { if m[i][j] == 1 { uf.union(i as i32, j as i32); } } } uf.count } }
Solutions
Approach 2: DFS
-
Time complexity:
-
Space complexity:
-
Runtime: 0 ms
-
Memory: 2.7 MB
impl Solution { pub fn find_circle_num(m: Vec<Vec<i32>>) -> i32 { if m.is_empty() { return 0; } let n = m.len(); let mut visited: Vec<i32> = vec![]; let mut count = 0; for i in 0..n { if !visited.contains(&(i as i32)) { Self::dfs(&m, &mut visited, i, n); count += 1; } } count } pub fn dfs(m: &Vec<Vec<i32>>, visited: &mut Vec<i32>, i: usize, n: usize) { for j in 0..n { if m[i][j] == 1 && !visited.contains(&(j as i32)) { visited.push(j as i32); Self::dfs(m, visited, j, n); } } } }