Number of Provinces
Problem
isConnected[i][j] = 1 means cities i and j are directly connected. A province is a group of cities connected directly or indirectly. Return the number of provinces.
Example 1
Input: [[1,1,0], [1,1,0], [0,0,1]] Output: 2
Test cases
Case 1
Input: [[1,1,0],[1,1,0],[0,0,1]] Expected: 2
Case 2
Input: [[1,0,0],[0,1,0],[0,0,1]] Expected: 3
Case 3
Input: [[1]] Expected: 1
View solutionHide solution1 approach
1. DFS on the adjacency matrix
Time O(n²)Space O(n)
Count how many DFS starts are needed to visit every city.
function findCircleNum(M) { const n = M.length, seen = new Array(n).fill(false); const dfs = (i) => { seen[i] = true; for (let j = 0; j < n; j++) if (M[i][j] && !seen[j]) dfs(j); }; let count = 0; for (let i = 0; i < n; i++) if (!seen[i]) { count++; dfs(i); } return count;}