Code Implementation

class Solution:
    def findCircleNum(self, isConnected):
        n = len(isConnected)
        visited = [False] * n

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

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

class Solution {
public:
    void dfs(int city, vector<vector<int>>& isConnected, vector<bool>& visited) {
        int n = isConnected.size();
        for (int neighbor = 0; neighbor < n; ++neighbor) {
            if (isConnected[city][neighbor] == 1 && !visited[neighbor]) {
                visited[neighbor] = true;
                dfs(neighbor, isConnected, visited);
            }
        }
    }
    int findCircleNum(vector<vector<int>>& isConnected) {
        int n = isConnected.size();
        vector<bool> visited(n, false);
        int provinces = 0;
        for (int i = 0; i < n; ++i) {
            if (!visited[i]) {
                visited[i] = true;
                dfs(i, isConnected, visited);
                provinces++;
            }
        }
        return provinces;
    }
};
      

class Solution {
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        boolean[] visited = new boolean[n];
        int provinces = 0;
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs(isConnected, visited, i);
                provinces++;
            }
        }
        return provinces;
    }
    private void dfs(int[][] isConnected, boolean[] visited, int city) {
        for (int neighbor = 0; neighbor < isConnected.length; neighbor++) {
            if (isConnected[city][neighbor] == 1 && !visited[neighbor]) {
                visited[neighbor] = true;
                dfs(isConnected, visited, neighbor);
            }
        }
    }
}
      

var findCircleNum = function(isConnected) {
    const n = isConnected.length;
    const visited = new Array(n).fill(false);

    function dfs(city) {
        for (let neighbor = 0; neighbor < n; neighbor++) {
            if (isConnected[city][neighbor] === 1 && !visited[neighbor]) {
                visited[neighbor] = true;
                dfs(neighbor);
            }
        }
    }

    let provinces = 0;
    for (let i = 0; i < n; i++) {
        if (!visited[i]) {
            visited[i] = true;
            dfs(i);
            provinces++;
        }
    }
    return provinces;
};
      

Problem Description

The "Number of Provinces" problem asks you to determine how many groups of directly or indirectly connected cities exist, given a 2D matrix isConnected. Each element isConnected[i][j] is 1 if city i and city j are directly connected, and 0 otherwise. A province is defined as a group of cities that are directly or indirectly connected, and no other cities outside the group are connected to any city within the group.

• The input is a square matrix representing the connections between n cities.
• Each city is connected to itself (diagonal elements are 1).
• Your task is to count the number of provinces, i.e., the number of connected groups.
• All cities belong to exactly one province.

Thought Process

When first approaching the problem, you might think to check every possible pair of cities to see if they're connected, but this quickly becomes inefficient as the number of cities grows. The key realization is that the matrix represents an undirected graph, where cities are nodes and connections are edges. The problem essentially asks for the number of connected components in this graph.

Brute-force would involve repeatedly checking every possible path between cities, but this is redundant and slow. Instead, we can use graph traversal techniques such as Depth-First Search (DFS), Breadth-First Search (BFS), or Union-Find (Disjoint Set Union) to efficiently group cities and count the number of distinct provinces.

The main insight is: once we start visiting a city, we can use DFS (or BFS) to mark all cities in its province as visited, so we don't count them again.

Solution Approach

Let's break down the steps to solve the problem using DFS (the most straightforward approach for beginners):

1. Initialize a visited array: This keeps track of which cities have already been assigned to a province.
2. Iterate over all cities: For each city, if it hasn't been visited, we know we've found a new province.
3. DFS Traversal: When a new province is found, perform a DFS starting from that city. Mark all reachable cities as visited (i.e., mark all cities in the same province).
4. Count provinces: Each time a DFS starts from an unvisited city, increment the province count.

We use DFS here because it's easy to implement recursively and efficiently explores all connected nodes. The visited array ensures we don't revisit cities, preventing infinite loops and redundant counting.

Alternative approaches include BFS (using a queue) or Union-Find, but the core idea remains: group connected cities and count the groups.

Example Walkthrough

Let's consider the following input:

    isConnected = [
      [1, 1, 0],
      [1, 1, 0],
      [0, 0, 1]
    ]
  

• Start with city 0. It's unvisited, so we start DFS. City 0 is connected to city 1 (since isConnected[0][1] == 1).
• Mark cities 0 and 1 as visited. City 1 is also connected back to city 0, but it's already visited.
• City 2 is not connected to city 0 or 1. It's unvisited, so we start a new DFS from city 2, marking it as visited.
• We have started DFS twice, so the answer is 2 provinces.

Time and Space Complexity

• Brute-force: Checking all pairs for connectivity can take up to O(n³) time due to repeated traversals.
• Optimized (DFS/BFS): Each city and connection is visited once, so the time complexity is O(n²), where n is the number of cities.
• Space Complexity: O(n) for the visited array, and up to O(n) for the call stack in DFS.

The O(n²) comes from the need to potentially check every connection in the matrix, but each is only processed once.

Summary

The Number of Provinces problem is a classic application of graph traversal. By treating the input matrix as an adjacency matrix for an undirected graph, we can efficiently count the number of connected components (provinces) using DFS, BFS, or Union-Find. The key insight is to mark cities as visited as we traverse, ensuring each group is counted exactly once. This approach is both intuitive and efficient, making it a staple technique in graph algorithms.