547. Number of Provinces - Detailed Explanation

Problem Statement

There are n cities numbered from 0 to n−1. You are given an n × n isConnected matrix where isConnected[i][j] = 1 if the iᵗʰ and jᵗʰ cities are directly connected, and isConnected[i][j] = 0 otherwise. A province is a group of directly or indirectly connected cities (an undirected connected component). Return the total number of provinces.

Examples

Example 1

Input  
isConnected = [
  [1,1,0],
  [1,1,0],
  [0,0,1]
]
Output  
2

Explanation
Cities 0 and 1 are connected, forming one province; city 2 is isolated, forming a second.

Example 2

Input  
isConnected = [
  [1,0,0],
  [0,1,0],
  [0,0,1]
]
Output  
3

Explanation
No two distinct cities are connected, so each forms its own province.

Constraints

• 1 ≤ n = isConnected.length = isConnected[i].length ≤ 200
• isConnected[i][i] = 1 for all i
• isConnected[i][j] = isConnected[j][i] ∈ {0,1}

Intuition

This is just counting connected components in an undirected graph given as an adjacency matrix. You can either:

• DFS/BFS from each unvisited city, marking all reachable cities as visited and incrementing your province count
• Union‑Find (Disjoint Set Union) to union every pair of directly connected cities, then count distinct roots

Depth‑First Search Approach

Explanation

1. Maintain a visited array of size n.
2. For each city i from 0…n−1, if it’s not visited, start a DFS to mark every city reachable from i.
3. After each DFS, you’ve discovered one province, so increment count.

Algorithm

count = 0
visited = [false] * n
for i in 0…n−1:
  if not visited[i]:
    dfs(i)
    count += 1

function dfs(u):
  visited[u] = true
  for v in 0…n−1:
    if isConnected[u][v] == 1 and not visited[v]:
      dfs(v)

Step‑by‑Step Walkthrough

isConnected = [
  [1,1,0],
  [1,1,0],
  [0,0,1]
]

• i=0: not visited → dfs(0) marks 0, then sees v=1 is connected → dfs(1) marks 1. Returns → count=1
• i=1: already visited → skip
• i=2: not visited → dfs(2) marks 2 → count=2
  Return 2

Union‑Find Approach

Explanation

1. Initialize parent[i]=i for all i, and count = n (each city is its own province).
2. For every pair (i,j) with isConnected[i][j]==1, union(i,j); if they had different roots, decrement count.
3. At the end, count equals number of provinces.

Algorithm

parent[i] = i for i in 0…n−1
count = n

function find(x):
  while parent[x] != x:
    parent[x] = parent[parent[x]]
    x = parent[x]
  return x

function union(a,b):
  ra = find(a), rb = find(b)
  if ra != rb:
    parent[rb] = ra
    count -= 1

for i in 0…n−1:
  for j in i+1…n−1:
    if isConnected[i][j] == 1:
      union(i, j)

return count

Complexity Analysis

• Time
  • DFS/BFS: O(n²) in worst case (adjacency‑matrix scan per node)
  • Union‑Find: O(n² · α(n)) ≈ O(n²)
• Space
  • O(n²) for input, O(n) extra for visited or parent arrays