Number of Provinces
Description
There are n cities. Some of them are connected directly, 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, with no other cities outside of the group.
You are given an n × n matrix isConnected where isConnected[i][j] = 1 means the i-th city and the j-th city are directly connected, and isConnected[i][j] = 0 means they are not.
Return the total number of provinces.
Examples
Example 1
Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]]
Output: 2
Explanation: City 0 and city 1 are directly connected (isConnected[0][1] = 1), so they belong to the same province. City 2 is not connected to either city 0 or city 1, so it forms its own separate province. Therefore, there are 2 provinces in total.
Example 2
Input: isConnected = [[1,0,0],[0,1,0],[0,0,1]]
Output: 3
Explanation: No city is connected to any other city. Each city forms its own province — city 0 alone, city 1 alone, and city 2 alone. That gives us 3 provinces.
Example 3
Input: isConnected = [[1,1,0,0],[1,1,1,0],[0,1,1,0],[0,0,0,1]]
Output: 2
Explanation: City 0 connects to city 1, and city 1 connects to city 2, so cities 0, 1, and 2 are all indirectly connected and form one province. City 3 has no connections to any other city, forming a second province. Total: 2 provinces.
Constraints
- 1 ≤ n ≤ 200
- n == isConnected.length
- n == isConnected[i].length
- isConnected[i][j] is 0 or 1
- isConnected[i][i] == 1
- isConnected[i][j] == isConnected[j][i]
Editorial
Brute Force
Intuition
Think of each city as a person in a room, and the adjacency matrix tells you who is friends with whom. A province is a group of people who are all connected through chains of friendship.
The simplest approach is: pick any unvisited city, then explore all cities reachable from it by following direct connections. Every city you reach belongs to the same province. Once you exhaust all reachable cities, you have found one complete province. Then pick the next unvisited city and repeat. Each time you start a new exploration from an unvisited city, that is a new province.
We use Depth-First Search (DFS) for this exploration. DFS works like following one chain of friends as deep as possible before backtracking — if city 0 connects to city 1, and city 1 connects to city 2, DFS will follow 0 → 1 → 2 before trying other connections from city 0.
Step-by-Step Explanation
Let's trace through with isConnected = [[1,1,0],[1,1,0],[0,0,1]] (3 cities):
Step 1: Initialize a visited array of size 3, all set to false: visited = [false, false, false]. Set province count = 0.
Step 2: Start at city 0 (first unvisited city). This is the beginning of a new province. Increment count to 1. Start DFS from city 0.
Step 3: DFS at city 0 — mark visited[0] = true. Check all cities: isConnected[0][1] = 1 and visited[1] = false, so recurse into city 1.
Step 4: DFS at city 1 — mark visited[1] = true. Check all cities: isConnected[1][0] = 1 but visited[0] = true (skip). isConnected[1][2] = 0 (no connection). No more unvisited neighbors. Backtrack.
Step 5: Back at city 0 DFS — check city 2: isConnected[0][2] = 0 (no connection). DFS from city 0 is complete. Province 1 contains cities {0, 1}.
Step 6: Move to city 1 in main loop — already visited. Skip.
Step 7: Move to city 2 in main loop — unvisited! This is a new province. Increment count to 2. Start DFS from city 2.
Step 8: DFS at city 2 — mark visited[2] = true. Check all cities: isConnected[2][0] = 0, isConnected[2][1] = 0. No neighbors. DFS complete. Province 2 contains city {2}.
Step 9: All cities visited. Return count = 2.
DFS Province Counting — Exploring Connected Cities — Watch DFS explore cities from the adjacency matrix, marking visited cities and counting each new province when an unvisited city is found.
Algorithm
- Create a
visitedboolean array of sizen, initialized tofalse - Initialize
provinces = 0 - For each city
ifrom0ton-1:- If
visited[i]isfalse:- Increment
provincesby 1 - Run DFS starting from city
i
- Increment
- If
- DFS(city):
- Mark
visited[city] = true - For each city
jfrom0ton-1:- If
isConnected[city][j] == 1andvisited[j] == false:- Recursively call DFS(j)
- If
- Mark
- Return
provinces
Code
class Solution {
public:
void dfs(vector<vector<int>>& isConnected, vector<bool>& visited, int city) {
visited[city] = true;
for (int j = 0; j < isConnected.size(); j++) {
if (isConnected[city][j] == 1 && !visited[j]) {
dfs(isConnected, visited, j);
}
}
}
int findCircleNum(vector<vector<int>>& isConnected) {
int n = isConnected.size();
vector<bool> visited(n, false);
int provinces = 0;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
provinces++;
dfs(isConnected, visited, i);
}
}
return provinces;
}
};class Solution:
def findCircleNum(self, isConnected: list[list[int]]) -> int:
n = len(isConnected)
visited = [False] * n
provinces = 0
def dfs(city: int) -> None:
visited[city] = True
for j in range(n):
if isConnected[city][j] == 1 and not visited[j]:
dfs(j)
for i in range(n):
if not visited[i]:
provinces += 1
dfs(i)
return provincesclass Solution {
public int findCircleNum(int[][] isConnected) {
int n = isConnected.length;
boolean[] visited = new boolean[n];
int provinces = 0;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
provinces++;
dfs(isConnected, visited, i);
}
}
return provinces;
}
private void dfs(int[][] isConnected, boolean[] visited, int city) {
visited[city] = true;
for (int j = 0; j < isConnected.length; j++) {
if (isConnected[city][j] == 1 && !visited[j]) {
dfs(isConnected, visited, j);
}
}
}
}Complexity Analysis
Time Complexity: O(n²)
For each city, DFS scans the entire row of the adjacency matrix (n entries) to find neighbors. Since every city is visited exactly once by DFS, the total work across all DFS calls is n × n = O(n²). The outer loop also runs n times, but the DFS work dominates.
Space Complexity: O(n)
We use a visited array of size n. The DFS recursion stack can go at most n levels deep (if all cities form one long chain). So total auxiliary space is O(n).
Why This Approach Is Not Efficient
The DFS approach runs in O(n²) time because it must scan the full adjacency matrix. For n ≤ 200, that is at most 40,000 operations, which is very fast.
However, conceptually the DFS approach uses recursion, which consumes O(n) stack space and can hit stack overflow for very deep chains. An iterative BFS approach avoids deep recursion while maintaining the same time complexity.
More importantly, if this problem were extended to a dynamic setting — where cities and connections are added over time and we need to answer "how many provinces?" after each update — DFS would need to re-explore the entire graph from scratch every time. This motivates the Union-Find approach, which handles incremental updates efficiently.
Better Approach - BFS
Intuition
Instead of using recursive DFS, we can use Breadth-First Search (BFS) to discover all cities in a province. BFS explores cities layer by layer — first all direct neighbors, then all neighbors-of-neighbors, and so on.
Imagine sending a message to all your direct friends, then each friend forwards it to their friends, and so on. Everyone who eventually receives the message is in your province.
BFS uses a queue instead of recursion, which avoids potential stack overflow issues with very large connected components. The logic remains the same: start from an unvisited city, explore everything reachable, count that as one province.
Step-by-Step Explanation
Let's trace through with isConnected = [[1,1,0],[1,1,0],[0,0,1]] (3 cities):
Step 1: Initialize visited = [false, false, false], provinces = 0. Create an empty queue.
Step 2: i=0 is unvisited. Increment provinces to 1. Enqueue city 0, mark visited[0] = true.
Step 3: Dequeue city 0. Scan row 0 of matrix: isConnected[0][1] = 1 and city 1 is unvisited. Enqueue city 1, mark visited[1] = true.
Step 4: Continue scanning row 0: isConnected[0][2] = 0. No more neighbors for city 0.
Step 5: Dequeue city 1. Scan row 1: isConnected[1][0] = 1 but city 0 visited (skip). isConnected[1][2] = 0 (no connection). No new cities enqueued.
Step 6: Queue is empty. Province 1 = {0, 1} is complete.
Step 7: i=1 is visited (skip). i=2 is unvisited. Increment provinces to 2. Enqueue city 2, mark visited[2] = true.
Step 8: Dequeue city 2. Scan row 2: isConnected[2][0] = 0, isConnected[2][1] = 0. No neighbors. Queue empty. Province 2 = {2}.
Step 9: All cities visited. Return 2.
BFS Province Counting — Layer-by-Layer Exploration — Watch BFS use a queue to explore cities level by level, discovering all cities in each province before moving to the next.
Algorithm
- Create a
visitedboolean array of sizen, allfalse - Initialize
provinces = 0 - For each city
ifrom0ton-1:- If
visited[i]isfalse:- Increment
provinces - Create a queue, enqueue
i, markvisited[i] = true - While queue is not empty:
- Dequeue city
curr - For each city
jfrom0ton-1:- If
isConnected[curr][j] == 1andvisited[j] == false:- Mark
visited[j] = true - Enqueue
j
- Mark
- If
- Dequeue city
- Increment
- If
- Return
provinces
Code
class Solution {
public:
int findCircleNum(vector<vector<int>>& isConnected) {
int n = isConnected.size();
vector<bool> visited(n, false);
int provinces = 0;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
provinces++;
queue<int> q;
q.push(i);
visited[i] = true;
while (!q.empty()) {
int curr = q.front();
q.pop();
for (int j = 0; j < n; j++) {
if (isConnected[curr][j] == 1 && !visited[j]) {
visited[j] = true;
q.push(j);
}
}
}
}
}
return provinces;
}
};from collections import deque
class Solution:
def findCircleNum(self, isConnected: list[list[int]]) -> int:
n = len(isConnected)
visited = [False] * n
provinces = 0
for i in range(n):
if not visited[i]:
provinces += 1
queue = deque([i])
visited[i] = True
while queue:
curr = queue.popleft()
for j in range(n):
if isConnected[curr][j] == 1 and not visited[j]:
visited[j] = True
queue.append(j)
return provincesclass Solution {
public int findCircleNum(int[][] isConnected) {
int n = isConnected.length;
boolean[] visited = new boolean[n];
int provinces = 0;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
provinces++;
Queue<Integer> queue = new LinkedList<>();
queue.offer(i);
visited[i] = true;
while (!queue.isEmpty()) {
int curr = queue.poll();
for (int j = 0; j < n; j++) {
if (isConnected[curr][j] == 1 && !visited[j]) {
visited[j] = true;
queue.offer(j);
}
}
}
}
}
return provinces;
}
}Complexity Analysis
Time Complexity: O(n²)
Same as DFS. Each city is dequeued exactly once, and for each dequeued city we scan its entire row of size n in the adjacency matrix. Total work = n cities × n checks per city = O(n²).
Space Complexity: O(n)
The visited array uses O(n) space. The queue can hold at most n cities simultaneously (if all cities are in one province). Total: O(n). Unlike DFS, there is no recursion stack, so this approach is safer for very large connected components.
Why This Approach Is Not Efficient
BFS has the same O(n²) time complexity as DFS. Both must scan the entire adjacency matrix. For the static version of this problem, both are perfectly efficient.
However, consider a dynamic scenario: if new connections are added between cities over time, both DFS and BFS would need to restart from scratch to recount provinces. Neither approach can handle incremental updates — they always process the full matrix.
The Union-Find (Disjoint Set Union) data structure solves this elegantly. It processes each edge once during construction and supports near-constant time union and find operations. While both approaches are O(n²) for this specific problem (because we must read every entry of the n×n matrix), Union-Find is the standard technique for connected component problems and scales better in edge-list representations.
Optimal Approach - Union-Find (Disjoint Set Union)
Intuition
Think of Union-Find like a team registration system. Initially, every city is its own team captain (its own province). When we discover that two cities are connected, we merge their teams — one captain becomes the sub-captain under the other.
To find which province a city belongs to, we follow the chain of captains until we reach the ultimate leader (the root). Two cities are in the same province if and only if they share the same root.
The key optimizations that make Union-Find nearly O(1) per operation are:
-
Path compression: When finding the root, we make every node along the path point directly to the root. This flattens the tree, so future lookups are instant.
-
Union by rank: When merging two trees, we attach the shorter tree under the taller one. This prevents the tree from becoming a long chain.
We start with n separate provinces (each city is its own province). For each pair (i, j) where isConnected[i][j] = 1, we union cities i and j. Each successful union (where the two cities were previously in different provinces) reduces the province count by 1. The final count is our answer.
Step-by-Step Explanation
Let's trace with isConnected = [[1,1,0],[1,1,0],[0,0,1]] (3 cities):
Step 1: Initialize Union-Find: parent = [0, 1, 2], rank = [0, 0, 0], provinces = 3. Each city is its own root.
Step 2: Process isConnected[0][1] = 1. Find root of city 0 → 0. Find root of city 1 → 1. Roots differ! Union them: attach city 1 under city 0 (both rank 0, so parent[1] = 0, rank[0] becomes 1). Provinces decreases to 2.
Step 3: Process isConnected[0][2] = 0. Not connected. Skip.
Step 4: Process isConnected[1][0] = 1. Find root of city 1 → follow parent[1]=0, root is 0. Find root of city 0 → 0. Same root! Already in the same province. No union needed.
Step 5: Process isConnected[1][2] = 0. Not connected. Skip.
Step 6: Process isConnected[2][0] = 0. Not connected. Skip.
Step 7: Process isConnected[2][1] = 0. Not connected. Skip.
Step 8: All pairs processed. Provinces = 2. Province 1: cities {0, 1} (root 0). Province 2: city {2} (root 2).
Union-Find — Merging Cities Into Provinces — Watch how Union-Find starts with each city as its own province and merges connected cities, reducing the province count with each successful union.
Algorithm
- Initialize Union-Find:
parent[i] = ifor all cities (each is its own root)rank[i] = 0for all citiesprovinces = n
- For each pair (i, j) where i < j:
- If
isConnected[i][j] == 1:- Find root of city i (with path compression)
- Find root of city j (with path compression)
- If roots differ: union them (by rank), decrement
provinces
- If
- Return
provinces
Find with path compression:
- If
parent[x] != x, setparent[x] = find(parent[x])recursively - Return
parent[x]
Union by rank:
- If
rank[rootA] < rank[rootB]: attach rootA under rootB - Else if
rank[rootA] > rank[rootB]: attach rootB under rootA - Else: attach rootB under rootA and increment
rank[rootA]
Code
class Solution {
public:
vector<int> parent, rank_;
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
bool unite(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) return false;
if (rank_[rootX] < rank_[rootY]) {
parent[rootX] = rootY;
} else if (rank_[rootX] > rank_[rootY]) {
parent[rootY] = rootX;
} else {
parent[rootY] = rootX;
rank_[rootX]++;
}
return true;
}
int findCircleNum(vector<vector<int>>& isConnected) {
int n = isConnected.size();
parent.resize(n);
rank_.resize(n, 0);
for (int i = 0; i < n; i++) parent[i] = i;
int provinces = n;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (isConnected[i][j] == 1) {
if (unite(i, j)) {
provinces--;
}
}
}
}
return provinces;
}
};class Solution:
def findCircleNum(self, isConnected: list[list[int]]) -> int:
n = len(isConnected)
parent = list(range(n))
rank = [0] * n
def find(x: int) -> int:
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def unite(x: int, y: int) -> bool:
root_x = find(x)
root_y = find(y)
if root_x == root_y:
return False
if rank[root_x] < rank[root_y]:
parent[root_x] = root_y
elif rank[root_x] > rank[root_y]:
parent[root_y] = root_x
else:
parent[root_y] = root_x
rank[root_x] += 1
return True
provinces = n
for i in range(n):
for j in range(i + 1, n):
if isConnected[i][j] == 1:
if unite(i, j):
provinces -= 1
return provincesclass Solution {
private int[] parent;
private int[] rank;
private int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
private boolean unite(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) return false;
if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
return true;
}
public int findCircleNum(int[][] isConnected) {
int n = isConnected.length;
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
int provinces = n;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (isConnected[i][j] == 1) {
if (unite(i, j)) {
provinces--;
}
}
}
}
return provinces;
}
}Complexity Analysis
Time Complexity: O(n² · α(n))
We iterate over the upper triangle of the n×n matrix, which has n(n-1)/2 entries. For each connection found, we perform a find and unite operation. With path compression and union by rank, each find/unite runs in O(α(n)) amortized time, where α is the inverse Ackermann function — effectively constant (≤ 4 for any practical input). Total: O(n²) for scanning the matrix × O(α(n)) per union/find ≈ O(n²).
Space Complexity: O(n)
The parent and rank arrays each use O(n) space. No recursion stack is needed beyond the path compression calls (which are at most O(n) deep before compression flattens them). Total auxiliary space: O(n).