Number of Provinces

Explanation & Solution

Description

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.

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

Output: 2

Explanation: Cities 0 and 1 are connected to each other, forming one province. City 2 is on its own, forming a second province.

Constraints

1 <= n <= 200
n == isConnected.length
n == isConnected[i].length
isConnected[i][j] is 1 or 0
isConnected[i][i] == 1
isConnected[i][j] == isConnected[j][i]

Approach

Graphs pattern

1. Initialize Tracking Structures

Create a visited array of size n, all set to false
Initialize a provinces counter to 0
Purpose: track which cities have already been assigned to a province

2. Iterate Over All Cities

Loop through each city i from 0 to n - 1
If city i has not been visited, it belongs to a new province
Increment the provinces counter

3. DFS From Unvisited City

When we find an unvisited city, start a depth-first search from it
Mark the current city as visited
Check every other city neighbor in the adjacency matrix row
If isConnected[city][neighbor] === 1 and neighbor is not visited, recurse into neighbor

4. DFS Marks Entire Province

The DFS visits all cities reachable from the starting city
This covers both direct and indirect connections
Once DFS completes, the entire connected component (province) is marked as visited

5. Return the Count

After iterating through all cities, provinces holds the total number of connected components
Each time we started a new DFS, we discovered a new province

Key Insight

The adjacency matrix represents a graph where each city is a node
Finding provinces is equivalent to counting connected components
DFS from each unvisited node explores an entire component — every new DFS call means a new province

Time

O(n²)we examine every cell in the matrix

Space

O(n)visited array plus recursion stack

Visualization

Input:

Connected Components3 nodes, 1 edges

output—

Press play to start connected components

CurrentQueuedVisited

7 steps

Solution Code

Clone Graph

Rotting Oranges