Number of Provinces — DFS on Adjacency Matrix

Problem

There are n cities. An n x n isConnected matrix tells if city i and j are directly connected. Count the total number of provinces (connected components).

Approach — DFS on adjacency matrix

For each unvisited city, DFS through all its connected cities. Count DFS calls.

Time: O(n²) | Space: O(n)

Solutions

Python

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

C++

class Solution {
    void dfs(vector<vector<int>>& g, vector<bool>& vis, int i){
        vis[i]=true;
        for(int j=0;j<g.size();j++) if(g[i][j]==1&&!vis[j]) dfs(g,vis,j);
    }
public:
    int findCircleNum(vector<vector<int>>& g){
        int n=g.size(),cnt=0; vector<bool> vis(n,false);
        for(int i=0;i<n;i++) if(!vis[i]){dfs(g,vis,i);cnt++;}
        return cnt;
    }
};

Java — Union-Find

class Solution {
    int[] p;
    int find(int x){ return p[x]==x?x:(p[x]=find(p[x])); }
    public int findCircleNum(int[][] g){
        int n=g.length; p=new int[n];
        for(int i=0;i<n;i++) p[i]=i;
        int cnt=n;
        for(int i=0;i<n;i++) for(int j=i+1;j<n;j++)
            if(g[i][j]==1){int a=find(i),b=find(j);if(a!=b){p[a]=b;cnt--;}}
        return cnt;
    }
}

Complexity

Time: O(n²) | Space: O(n)