Problem Statement: You are given an undirected graph with V vertices, represented as an adjacency list. Two nodes u and v belong to the same province if there is a path from u to v or vice versa. Your task is to determine how many such provinces (connected components) exist in the graph.
Examples❯
Graph Object
Number of Provinces
Description
{0: [1], 1: [0], 2: []}
2
Nodes 0 and 1 are connected, node 2 is isolated → 2 provinces.
{0: [], 1: [], 2: []}
3
Each node is isolated → 3 provinces.
{0: [1, 2], 1: [0, 2], 2: [0, 1]}
1
All nodes are connected → 1 province.
{0: []}
1
Only one node → 1 province.
{}
0
No nodes → 0 provinces.
Solution❯
YouTube Video - Detailed Understanding of Solution
Understanding the Problem
We are given an undirected graph where each node represents a city, and edges represent direct connections between them. A province is a group of cities that are all connected directly or indirectly. In graph terms, this means we are looking for the number of connected components.
Our goal is to count how many such groups (or provinces) exist in the graph. We’ll do this using a graph traversal algorithm like DFS (Depth-First Search).
How We Solve It – Step by Step
Start with an empty visited set to keep track of nodes we've already explored.
Initialize provinceCount = 0.
Loop through every node in the graph:
If the node is not visited, it's the start of a new province.
We perform DFS from that node to visit all connected nodes.
After the DFS finishes, we increment provinceCount.
Once all nodes are processed, provinceCount gives us the number of provinces.
Remaining nodes (3, 4, 5) are already visited, so we skip them
Total provinces = 2
Incorporating Edge Cases
Case 1: Empty Graph
Input:{}
Explanation: No nodes exist → no provinces
Answer: 0
Case 2: All Nodes Are Isolated
Input:{1: [], 2: [], 3: []}
Explanation: Each node is its own province
Answer: 3
Case 3: Fully Connected Graph
Input:{1: [2, 3], 2: [1, 3], 3: [1, 2]}
Explanation: All nodes reachable → one big province
Answer: 1
Case 4: Multiple Groups
Input:{0: [1], 1: [0], 2: [], 3: [4], 4: [3]}
Explanation: (0,1), (3,4), and 2 form three separate groups
Answer: 3
Conclusion
Using DFS (or BFS), we can efficiently find all connected cities starting from each unvisited node and count how many such groups exist. That gives us the total number of provinces in the graph.
Algorithm Steps❯
Initialize a visited set to keep track of nodes we've already explored.
Initialize provinceCount = 0.
Loop through each node i in the graph:
If i is not in visited:
Perform DFS or BFS from node i.
During traversal, mark all reachable nodes as visited.
Increment provinceCount.
Return provinceCount.
Code
C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#define N 3
void dfs(int graph[N][N], int visited[N], int node) {
visited[node] = 1;
for (int i = 0; i < N; i++) {
if (graph[node][i] && !visited[i]) {
dfs(graph, visited, i);
}
}
}
int findProvinces(int graph[N][N]) {
int visited[N] = {0};
int provinces = 0;
for (int i = 0; i < N; i++) {
if (!visited[i]) {
dfs(graph, visited, i);
provinces++;
}
}
return provinces;
}
int main() {
int graph[N][N] = {
{1, 1, 0},
{1, 1, 0},
{0, 0, 1}
};
printf("Provinces: %d\n", findProvinces(graph));
return 0;
}
Time Complexity❯
Case
Time Complexity
Explanation
Best Case
O(V + E)
If all nodes are part of one province, DFS/BFS will still touch all nodes and edges once.
Average Case
O(V + E)
Each component is visited once, processing all its vertices and edges.
Worst Case
O(V + E)
When all nodes are isolated, we perform V DFS/BFS calls with no edge visits.
Space Complexity❯
O(V)
Explanation: We maintain a visited set of size V.
About the author
Mallikarjuna Mallisetty
General programming
Mallikarjuna shares practical programming tutorials and foundational concepts designed to help developers learn by building and experimenting.
