Number of Provinces

There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c.

A province is a group of directly or indirectly connected cities and no other cities outside of the group.

You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the ith city and the jth city are directly connected, and isConnected[i][j] = 0 otherwise.

Return the total number of provinces.

Practice Link

Examples#

Example 1: isConnected = [[1,1,0],[1,1,0],[0,0,1]]

Cities 1 and 2 form one province; city 3 is its own province. Output: 2

Example 2: isConnected = [[1,0,0],[0,1,0],[0,0,1]]

Each city is its own province. Output: 3

DFS#

A province is exactly a connected component of the city graph, so counting provinces reduces to counting how many times we must start a fresh DFS to cover all cities. We iterate over every city and, if it hasn't been visited yet, launch a DFS that marks every city reachable from it — one complete DFS call corresponds to one province. Because the input is an adjacency matrix (not a list), each DFS node must scan all n entries in its row to find neighbours, giving O(V²) time overall — the same as BFS below. DFS is slightly simpler to write recursively but risks stack overflow for very large n.

DFS Implementation#

class Solution {
public:
    void DFS(vector<vector<int>>& isConnected, vector<int> &visited, int source)
    {
        visited[source] = true;
        for(int i=0;i<isConnected.size();i++)
        {
            if(!visited[i] && isConnected[source][i]==1)
                DFS(isConnected, visited, i);
        }
    }

    int findCircleNum(vector<vector<int>>& isConnected) {
        int n = isConnected.size();
        vector<int> visited(n, false);
        int provinces=0;
        for(int i=0;i<n;i++)
        {
            if(!visited[i])
            {
                DFS(isConnected, visited, i);
                provinces++;
            }
                
        }
        return provinces;
    }
};

Complexities#

Time Complexity - O(V^2)

Space Complexity - O(n) recursion stack + visited

BFS#

BFS solves the same connected-component counting problem iteratively, avoiding the recursion-stack depth concern of DFS. Each time we find an unvisited city in the outer loop we push it into the queue and run BFS until the queue is empty — at that point every city in the same province has been marked visited. For each city dequeued we scan its entire row in the adjacency matrix to enqueue unvisited neighbours, so the time complexity is still O(V²). Compared to DFS, BFS is safer for large inputs and naturally explores cities in breadth-first (distance) order, which matters if we ever need shortest-hop distances rather than just component membership.

BFS Implementation#

class Solution {
public:

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

        queue<int> q;

        auto bfs = [&](queue<int> &q){
            while(!q.empty())
            {
                int currCity = q.front();
                q.pop();

                visited[currCity]= true;

                for(int destCity=0;destCity<n;destCity++)
                {
                    if(!visited[destCity] && isConnected[currCity][destCity]==1)
                        q.push(destCity);
                }
            }
        };

        for(int i=0;i<n;i++)
        {
            if(!visited[i])
            {
                q.push(i);
                bfs(q);
                provinces++;
            }
        }
        return provinces;
    }
};

Complexities#

Time Complexity - O(V^2)

Space Complexity - O(n) queue + visited

DFS vs BFS#