Number of Provinces

Problem in plain words

There are n cities. You get an n × n matrix where isConnected[i][j] = 1 means cities i and j have a direct road (the matrix is symmetric and the diagonal is all 1). Cities that can reach each other directly or through other cities form one province. Return how many provinces there are.

Example: with four cities where 0–1 and 2–3 are linked and nothing else, there are two provinces: {0, 1} and {2, 3}.

Intuition

A province is a connected component of an undirected graph given as an adjacency matrix. Every time you find a city that has not been visited yet, it belongs to a brand-new component: count it, then flood-fill the whole component with a DFS so none of its cities triggers another count.

Approach

1. Keep a visited array of size n and a counter provinces = 0.
2. Loop over every city i. If it is already visited, skip it.
3. Otherwise increment provinces and run a DFS from i.
4. In the DFS, scan row city of the matrix; for every j with isConnected[city][j] == 1 that is unvisited, mark it and continue the DFS from it.
5. Return provinces.

Dry run

Edges 0–1 and 2–3, n = 4.

Java solution

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]) {
                provinces++;
                visited[i] = true;
                dfs(isConnected, visited, i);
            }
        }
        return provinces;
    }

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

Python solution

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        n = len(isConnected)
        visited = [False] * n
        provinces = 0
        for start in range(n):
            if visited[start]:
                continue
            provinces += 1
            visited[start] = True
            stack = [start]
            while stack:
                city = stack.pop()
                for other in range(n):
                    if isConnected[city][other] == 1 and not visited[other]:
                        visited[other] = True
                        stack.append(other)
        return provinces

Complexity

Edge cases and common mistakes

• Counting edges or 1s — the answer is the number of components, not the number of roads.
• Counting inside the DFS — increment the counter only in the outer loop, when you start a new component.
• Isolated cities — a city connected only to itself is its own province; the outer loop handles it.
• Treating the matrix as directed — it is symmetric, so scanning one row per city is enough.