LeetCode 547: Number of Provinces
Problem 1 (Number of Provinces). 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 × n matrix isConnected where isConnected[i][j] = 1 if the ith city and the
j th city are directly connected, and isConnected[i][j] = 0 otherwise.
Return the total number of provinces.
1 Problem Analysis
This problem is equivalent to finding the number of connected components in an undirected graph.
The input is given as an adjacency matrix representation of the graph.
Input: n × n adjacency matrix
Output: Number of connected components (provinces)
Graph type: Undirected, unweighted
Time complexity goal: O(n2 )
Space complexity goal: O(n)
2 Solution Approaches
2.1 Approach 1: Depth-First Search (DFS)
Theorem 1. DFS can be used to traverse each connected component completely. Each time we
start a new DFS from an unvisited node, we discover a new province.
1
1 def findCircleNum ( isConnected ) :
2 n = len ( isConnected )
3 visited = [ False ] * n
4 provinces = 0
5
6 def dfs ( city ) :
7 visited [ city ] = True
8 for neighbor in range ( n ) :
9 if isConnected [ city ][ neighbor ] == 1 and not visited [ neighbor ]:
10 dfs ( neighbor )
11
12 for i in range ( n ) :
13 if not visited [ i ]:
14 dfs ( i )
15 provinces += 1
16
17 return provinces
Listing 1: DFS Solution
Time Complexity: O(n2 ) - we potentially check every entry in the matrix
Space Complexity: O(n) - for the visited array and recursion stack
2.2 Approach 2: Breadth-First Search (BFS)
1 from collections import deque
2
3 def findCircleNum ( isConnected ) :
4 n = len ( isConnected )
5 visited = [ False ] * n
6 provinces = 0
7
8 for i in range ( n ) :
9 if not visited [ i ]:
10 queue = deque ([ i ])
11 visited [ i ] = True
12
13 while queue :
14 city = queue . popleft ()
15 for neighbor in range ( n ) :
16 if isConnected [ city ][ neighbor ] == 1 and not visited [ neighbor ]:
17 visited [ neighbor ] = True
18 queue . append ( neighbor )
19
20 provinces += 1
21
22 return provinces
Listing 2: BFS Solution
Time Complexity: O(n2 )
Space Complexity: O(n) - for visited array and queue
2
2.3 Approach 3: Union-Find (Disjoint Set Union)
1 def findCircleNum ( isConnected ) :
2 n = len ( isConnected )
3 parent = list ( range ( n ) )
4 rank = [0] * n
5
6 def find ( x ) :
7 if parent [ x ] != x :
8 parent [ x ] = find ( parent [ x ])
9 return parent [ x ]
10
11 def union (x , y ) :
12 root_x , root_y = find ( x ) , find ( y )
13 if root_x != root_y :
14 if rank [ root_x ] < rank [ root_y ]:
15 parent [ root_x ] = root_y
16 elif rank [ root_x ] > rank [ root_y ]:
17 parent [ root_y ] = root_x
18 else :
19 parent [ root_y ] = root_x
20 rank [ root_x ] += 1
21
22 for i in range ( n ) :
23 for j in range ( i + 1 , n ) :
24 if isConnected [ i ][ j ] == 1:
25 union (i , j )
26
27 return len ( set ( find ( i ) for i in range ( n ) ) )
Listing 3: Union-Find Solution
Time Complexity: O(n2 · α(n)) where α is the inverse Ackermann function
Space Complexity: O(n)
2.4 Approach 4: Converting to Adjacency List
Although the input is given as an adjacency matrix, we can convert it to an adjacency list and then
apply graph traversal algorithms.
1 def findCircleNum ( isConnected ) :
2 n = len ( isConnected )
3
4 # Convert to adjacency list
5 adj_list = [[] for _ in range ( n ) ]
6 for i in range ( n ) :
7 for j in range ( n ) :
8 if isConnected [ i ][ j ] == 1 and i != j :
9 adj_list [ i ]. append ( j )
10
11 # Apply DFS on adjacency list
12 visited = [ False ] * n
13 provinces = 0
14
3
15 def dfs ( city ) :
16 visited [ city ] = True
17 for neighbor in adj_list [ city ]:
18 if not visited [ neighbor ]:
19 dfs ( neighbor )
20
21 for i in range ( n ) :
22 if not visited [ i ]:
23 dfs ( i )
24 provinces += 1
25
26 return provinces
Listing 4: Matrix to Adjacency List Conversion
3 Algorithm Comparison
Method Time Space Pros Cons
DFS (recursive) O(n2 ) O(n) Simple, intuitive Stack overflow risk
BFS O(n2 ) O(n) No recursion depth issues Queue overhead
Union-Find O(n2 α(n)) O(n) Good for dynamic queries More complex
Iterative DFS O(n2 ) O(n) No recursion limits Manual stack
Table 1: Comparison of different approaches
4 Example Walkthrough
Consider the input matrix:
1 1 0
isConnected = 1 1 0
0 0 1
Cities 0 and 1 are connected
City 2 is isolated
Total provinces = 2
5 Conclusion
The Number of Provinces problem is a classic connected components problem in graph theory.
While multiple approaches exist, DFS is typically the most straightforward and efficient solution
for this specific problem format. The choice of algorithm depends on the specific requirements such
as recursion depth limitations, need for dynamic connectivity queries, or memory constraints.
4
For LeetCode 547, since the input is given as an adjacency matrix and the graph is static, the direct
DFS approach on the matrix is recommended for its simplicity and optimal performance.
