547. Number of Provinces

Description of Problem

There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c.

A province is a group of directly or indirectly connected cities and no other cities outside of the group.

You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the ith city and the jth city are directly connected, and isConnected[i][j] = 0 otherwise.

Return the total number of provinces.

Example 1:

Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]]
Output: 2

Example 2:

Input: isConnected = [[1,0,0],[0,1,0],[0,0,1]]
Output: 3

Constraints:

1 <= n <= 200
n == isConnected.length
n == isConnected[i].length
isConnected[i][j] is 1 or 0.
isConnected[i][i] == 1
isConnected[i][j] == isConnected[j][i]

Solution

Tags: Depth First Search,Graph Theory

Explanation

Perform depth-first-search on each node until all nodes are explored:

Mark the current as gray node (exploring node).
Perform depth-first-search in adjancent white nodes (unexplored nodes).
When complete exploration of each adjancent white nodes, mark the current node as black node (explored node).

Since a depth-first-search from node i traverses all nodes that reachable from node i. Hence, the count of depth-first-search performed is the number of provinces.

Code (Rust)

#[derive(Clone, Copy, Debug, PartialEq)]
enum Colour{
    White,
    Gray,
    Black,
}
use Colour::{White, Gray, Black};

impl Solution {
    pub fn find_circle_num(is_connected: Vec<Vec<i32>>) -> i32 {
        let n = is_connected.len();
        let mut count = 0;
        let mut colour = vec![White ; n];
        for node in 0..n {
            if colour[node] == White{
                Self::dfs(node, &is_connected, &mut colour);
                count+=1;
            }

        }
        return count;
        
    }

    fn dfs(node : usize, is_connected : &Vec<Vec<i32>>, colour : &mut Vec<Colour>) {
        colour[node] = Gray;
        for (i, &b) in is_connected[node].iter().enumerate() {
            if b == 1 && colour[i] == White {
                Self::dfs(i, is_connected, colour);
            }
        }
        colour[node] = Black;
    }
}

Complexity

\(|V|\) is the number of nodes
\(|E|\) is the number of edges

Time Complexity

\( T(|V|,|E|) = \Theta(|V|) \)

Auxiliary Space

\(S(|V|,|E|) = \Theta(|V|)\)
- Keep track of node colours

Leetbook