Number of Provinces — Editorial

Opening the reading…

Intuitionwhy one search counts exactly one province

A province contains every city reachable from any one of its cities through direct connections. Therefore, if you start from a city and repeatedly follow every connection, the search visits the entire province containing that city. Once that search finishes, no unvisited city can belong to the same province, because every city in that province was reachable and has already been marked.

Scan the cities from index 0 to n - 1. When a city is already visited, an earlier search reached it, so it cannot begin a new province. When a city is unvisited, start one DFS and increase the answer once. The DFS may visit many cities, but the count increases only at the start, which makes the count equal to the number of connected groups.

One DFS marks a complete province, so only its starting city increments the answer.

Approachscan starts, traverse groups, count starts

Read n from the number of rows and create a visited array of size n, because the matrix describes n cities and every city needs exactly one visitation state.

Set the province count to zero, because no connected group has been discovered before the scan begins.

For each city i from 0 to n - 1, check visited[i], because an already visited city belongs to a province counted by an earlier search.

When i is unvisited, increment the province count and start DFS at i, because this is the first city encountered from a previously undiscovered province.

Mark the current city visited before exploring its neighbors, because marking after recursion can cause connected cities to revisit one another and can repeat work.

Inspect every city v in the current row and recurse only when isConnected[u][v] is 1 and v is unvisited, because these are exactly the direct edges that can lead to new members of the same province.

Return the count after the outer scan finishes, because every city has either started one search or been absorbed into a search started earlier.

Complexitythe matrix makes every row scan explicit

MEASURE	BOUND	WHY
Time	O(n^2)	Each city is visited once, and processing a visited city scans its entire matrix row of n possible neighbors. Across n rows, the algorithm examines at most n x n matrix entries; no adjacency-list conversion is needed.
Space	O(n) extra	The visited array uses O(n) space and the DFS call stack uses O(n) in the worst case when one province forms a chain of recursive calls. The returned integer is constant-size output and is not working memory.

Annotated solutionC++ · recursive DFS · one count per search start

CPPDFS marks the complete component of each unvisited city and counts that component once.

#include <functional>
#include <vector>

using namespace std;

class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        int n = static_cast<int>(isConnected.size());
        vector<bool> visited(n, false);
        int provinces = 0;

        function<void(int)> dfs = [&](int city) {
            visited[city] = true;

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

        for (int city = 0; city < n; city++) {
            if (!visited[city]) {
                provinces++;
                dfs(city);
            }
        }

        return provinces;
    }
};

The placement of the count increment matters as much as the DFS itself. provinces++ appears immediately before dfs(city), not inside the neighbor loop and not once per visited city. The outer loop identifies new components; the recursive function only discovers the rest of the component and records that those cities must not start another count.

The iterative alternativeBFS avoids recursive call-stack depth

CPPBFS uses an explicit queue to mark each province without recursive calls.

#include <queue>
#include <vector>

using namespace std;

class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        int n = static_cast<int>(isConnected.size());
        vector<bool> visited(n, false);
        int provinces = 0;
        queue<int> pending;

        for (int city = 0; city < n; city++) {
            if (visited[city]) {
                continue;
            }

            provinces++;
            visited[city] = true;
            pending.push(city);

            while (!pending.empty()) {
                int current = pending.front();
                pending.pop();

                for (int neighbor = 0; neighbor < n; neighbor++) {
                    if (isConnected[current][neighbor] && !visited[neighbor]) {
                        visited[neighbor] = true;
                        pending.push(neighbor);
                    }
                }
            }
        }

        return provinces;
    }
};

This is a different traversal arrangement, not a better asymptotic algorithm. BFS still examines the same matrix rows, so its time is O(n^2), and its queue plus visited array use O(n) extra space. It is useful when a province can contain many cities and you want to avoid the worst-case recursive depth of n; the traversal order changes, but the counting rule does not.