Number of Provinces

Medium

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}