Problem statement

There are n cities; isConnected[i][j] = 1 means cities i and j are directly connected. A province is a group of directly or indirectly connected cities.

Given the n x n symmetric matrix isConnected, return the number of provinces.

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

Constraints

• 1 <= n <= 10
• isConnected[i][i] == 1; the matrix is symmetric.

Hints for Number of Provinces

1. Hint 1

   Each unvisited city starts a new province — DFS/BFS marks its whole component.

2. Hint 2

   Union-Find also works: count the remaining roots.

How to solve Number of Provinces

A province is a connected component of the graph described by the adjacency matrix. Counting components is a standard sweep: walk the cities, and every time you meet one you have not visited yet, that city must belong to a component nobody has counted — so increment the answer and flood-fill everything reachable from it.

Approach

1. Keep a seen flag per city and a component counter at 0.
2. For each city i not yet seen: increment the counter, then start a DFS or BFS from i.
3. In the traversal, from city u visit every v with isConnected[u][v] == 1 that is not yet seen, marking it seen.
4. When the traversal drains, the whole province has been marked; continue the outer scan.
5. The counter is the number of provinces.

Why it works

Marking cities as seen the moment they are queued means each city is processed exactly once, so the traversal from i reaches precisely the cities connected to i and no others. The outer loop therefore starts a new traversal exactly once per component — never twice for the same one, because the second city of a component is already marked by the time the loop reaches it.

Complexity

• Time — O(n^2)
• Space — O(n)

Pitfalls

• Mark a city as seen when you push it, not when you pop it, or the same city can be queued many times.
• The diagonal is always 1; a self-loop is harmless here but must not be mistaken for a connection to another city.
• Union-Find is an equally good fit — count the distinct roots at the end rather than the traversals.

Reference solution

Python

from typing import List

def findCircleNum(isConnected: List[List[int]]) -> int:
    n = len(isConnected)
    seen = [False] * n

    def dfs(i):
        seen[i] = True
        for j in range(n):
            if isConnected[i][j] == 1 and not seen[j]:
                dfs(j)

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

Java

public static int findCircleNum(int[][] isConnected) {
    int n = isConnected.length;
    boolean[] seen = new boolean[n];
    int provinces = 0;
    for (int i = 0; i < n; i++) {
        if (seen[i]) continue;
        provinces++;
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(i);
        seen[i] = true;
        while (!stack.isEmpty()) {
            int u = stack.pop();
            for (int v = 0; v < n; v++) {
                if (isConnected[u][v] == 1 && !seen[v]) {
                    seen[v] = true;
                    stack.push(v);
                }
            }
        }
    }
    return provinces;
}

C++

int findCircleNum(vector<vector<int>>& isConnected) {
    int n = (int) isConnected.size();
    vector<bool> seen(n, false);
    int provinces = 0;
    for (int i = 0; i < n; i++) {
        if (seen[i]) continue;
        provinces++;
        vector<int> stack;
        stack.push_back(i);
        seen[i] = true;
        while (!stack.empty()) {
            int u = stack.back();
            stack.pop_back();
            for (int v = 0; v < n; v++) {
                if (isConnected[u][v] == 1 && !seen[v]) {
                    seen[v] = true;
                    stack.push_back(v);
                }
            }
        }
    }
    return provinces;
}

JavaScript

var findCircleNum = function(isConnected) {
    const n = isConnected.length;
    const seen = new Array(n).fill(false);
    function dfs(i) {
        seen[i] = true;
        for (let j = 0; j < n; j++) {
            if (isConnected[i][j] === 1 && !seen[j]) dfs(j);
        }
    }
    let count = 0;
    for (let i = 0; i < n; i++) {
        if (!seen[i]) {
            count++;
            dfs(i);
        }
    }
    return count;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More depth-first search problems

• Minimize Maximum Component Cost Medium
• Minimum Time for K Connected Components Medium
• Power Grid Maintenance Medium
• Minimum Time to Reach Destination in Directed Graph Medium
• Unit Conversion I Medium
• Digit Operations to Make Two Integers Equal Medium