Number of Provinces

Problem

You have an n x n adjacency matrix where isConnected[i][j] = 1 means cities i and j are directly connected. Provinces are connected components. Return the number of provinces.

Constraints

• 1 ≤ n ≤ 200

Approach — Graphs

This is a Graphs problem. The idea: explore the graph with BFS or DFS, marking nodes visited so you never process one twice. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(V + E) time.

Solution code

Python

class Solution:
    def findCircleNum(self, isConnected):
        n = len(isConnected)
        seen = [False] * n
        def dfs(i):
            seen[i] = True
            for j in range(n):
                if isConnected[i][j] and not seen[j]:
                    dfs(j)
        count = 0
        for i in range(n):
            if not seen[i]:
                count += 1
                dfs(i)
        return count

Java

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) {
        visited[city] = true;
        for (int next = 0; next < isConnected.length; next++) {
            if (isConnected[city][next] == 1 && !visited[next]) {
                dfs(isConnected, visited, next);
            }
        }
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.