Number Of Provinces - Leetcode Solution

Problem Statement:

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

Solution:

The problem can be approached by using Depth First Search (DFS) algorithm.

1. We start with a city, mark it as visited and perform DFS on all the cities that are directly or indirectly connected to it.

2. While performing DFS, we mark all the visited cities, which are directly or indirectly connected to it, as visited.

3. Then we move to the next unvisited city and repeat the process until all cities are visited.

4. The number of times we perform DFS is equal to the total number of provinces, and this is the answer to the problem.

Code:

The Java code for the problem can be written as follows:

class Solution { public int findCircleNum(int[][] isConnected) {

    int n = isConnected.length;
    boolean[] visited = new boolean[n];
    int count = 0;

    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            dfs(isConnected, visited, i);
            count++;
        }
    }
    return count;
}

private void dfs(int[][] isConnected, boolean[] visited, int city) {
    visited[city] = true;

    for (int i = 0; i < isConnected.length; i++) {
        if (isConnected[city][i] == 1 && !visited[i]) {
            dfs(isConnected, visited, i);
        }
    }
}

}

Time Complexity:

The time complexity of the code is O(n^2), where n is the number of cities. As we have to traverse the matrix, which is O(n^2), and perform DFS on the cities, which is O(n), the total time complexity is O(n^2) + O(n) = O(n^2).

1