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