LeetCode Solutions Blog

Number of Provinces

Number: 547

Difficulty: Medium

Paid? No

Problem Description

Given an n x n matrix isConnected where isConnected[i][j] = 1 means city i is directly connected to city j (and 0 otherwise), find the total number of provinces. A province is a group of directly or indirectly connected cities.

Key Insights

The matrix represents an undirected graph where each node is a city.
Direct and indirect connections imply finding connected components in the graph.
DFS, BFS, or Union-Find can be used to traverse and count connected components.
Each traversal starting from an unvisited city represents a new province.

Space and Time Complexity

Time Complexity: O(n^2) – Every cell of the matrix is inspected. Space Complexity: O(n) – For the visited array (and recursion stack in DFS worst-case).

Solution

To solve the problem, we use a Depth-First Search (DFS) approach. Start by iterating over each city. When encountering an unvisited city, initiate a DFS to mark all cities within the same province as visited. Increment the province counter for each DFS initiation. This effectively counts the number of connected components (provinces) in the graph.

Code Solutions

Python:

JavaScript:

C++:

Java:

# Function to count the number of provinces using DFS
def findCircleNum(isConnected):
    n = len(isConnected)  # Total number of cities
    visited = [False] * n  # Track visited cities

    # Helper function for Depth-First Search
    def dfs(city):
        visited[city] = True  # Mark the current city as visited
        # Explore all neighbors of the current city
        for neighbor in range(n):
            # If the neighbor is connected and not visited yet, explore deeper
            if isConnected[city][neighbor] == 1 and not visited[neighbor]:
                dfs(neighbor)

    provinces = 0  # Initialize province counter
    # Iterate over each city
    for city in range(n):
        if not visited[city]:
            dfs(city)  # Start DFS for a new province
            provinces += 1  # Increment province count
    return provinces

# Example usage:
if __name__ == "__main__":
    isConnected = [[1, 1, 0], [1, 1, 0], [0, 0, 1]]
    print(findCircleNum(isConnected))  # Expected Output: 2