Number of Provinces

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 i<sup>th</sup> city and the j<sup>th</sup> city are directly connected, and isConnected[i][j] = 0 otherwise.

Return the total number of provinces.

For example: isConnected = [[1,1,0],[1,1,0],[0,0,1]] Output: 2

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

Question: Number of Provinces

Given an n x n matrix isConnected representing connections between cities, where isConnected[i][j] = 1 if the i-th city and the j-th city are directly connected, and isConnected[i][j] = 0 otherwise, determine the total number of provinces. A province is a group of directly or indirectly connected cities.

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

Naive Solution: Depth-First Search (DFS)

The most straightforward approach is to iterate through each city and use Depth-First Search (DFS) to explore all connected cities. Each time we start a DFS from an unvisited city, we've found a new province. We mark visited cities during the DFS to avoid recounting them.

Code (Python):

def findCircleNum_naive(isConnected):
    n = len(isConnected)
    visited = [False] * n
    count = 0

    def dfs(city):
        visited[city] = True
        for neighbor in range(n):
            if isConnected[city][neighbor] == 1 and not visited[neighbor]:
                dfs(neighbor)

    for i in range(n):
        if not visited[i]:
            dfs(i)
            count += 1
    return count

Optimal Solution: Depth-First Search (DFS)

The optimal solution also leverages DFS, with a slight refinement to improve readability and maintainability, while having the same time and space complexity as the naive approach.

Code (Python):

def findCircleNum(isConnected):
    n = len(isConnected)
    visited = [False] * n
    province_count = 0

    def dfs(city):
        visited[city] = True
        for neighbor in range(n):
            if isConnected[city][neighbor] == 1 and not visited[neighbor]:
                dfs(neighbor)

    for city in range(n):
        if not visited[city]:
            dfs(city)
            province_count += 1

    return province_count

Big(O) Run-time Analysis

The time complexity is O(n^2), where n is the number of cities. This is because, in the worst case, we might have to traverse the entire isConnected matrix during the DFS for each city. The outer loop iterates n times, and the inner loop (DFS) can iterate up to n times in the worst case where all cities are connected, giving O(n*n) = O(n^2).

Big(O) Space Usage Analysis

The space complexity is O(n). This comes from the visited array, which stores a boolean value for each city (n cities). In the worst case, the DFS recursion stack can also reach a depth of n if all cities are connected in a single province. Therefore, the space complexity is dominated by O(n).

Edge Cases

1. Empty Input: If the input matrix isConnected is empty (n=0), then there are no cities and thus no provinces. The code handles this implicitly as the loops won't execute and the function will return 0.
2. Single City: If there is only one city (n=1), then there is one province. The code correctly identifies this because the DFS will be called once.
3. No Connections: If there are no connections between any cities (other than the self-connections), each city forms its own province. The code accurately counts this as the DFS will only visit the starting city each time.
4. Fully Connected Graph: If all cities are connected to each other, there is only one province. The DFS will explore all cities starting from the first city, and the count will be incremented only once.
5. Disjointed Subgraphs: The graph may contain several disjointed subgraphs (provinces). The code correctly identifies each of these subgraphs using the visited array to ensure we explore each city only once.