Number of Provinces
Problem 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.
Example 1:
Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]]
Output: 2
Example 2:
Input: isConnected = [[1,0,0],[0,1,0],[0,0,1]]
Output: 3
Constraints:
1 <= n <= 200n == isConnected.lengthn == isConnected[i].lengthisConnected[i][j]is1or0.isConnected[i][i] == 1isConnected[i][j] == isConnected[j][i]
Solve it on LeetCode
Approaches
1. Depth-First Search (DFS)
Intuition:
The problem can be conceptualized as finding connected components in an undirected graph. Each city is a node, and a direct road between two cities is an edge. Using Depth-First Search, we can explore all nodes (i.e., cities) connected to a starting node, marking them as visited. Each new unvisited node indicates the start of a new province.
Code:
- Time Complexity: O(n^2): We visit each cell in the matrix isConnected exactly once.
- Space Complexity: O(n): The space for the visited array and the call stack in the worst case (when the graph is a single connected component).
2. Breadth-First Search (BFS)
Intuition:
Similar to the DFS approach, we aim to find connected components. However, BFS uses a queue to explore all nodes extensively level by level. Whenever we find a new city that hasn't been visited, we add it to the queue and mark it as part of the same province.
Code:
- Time Complexity: O(n^2) - Every city and every possible connection (road) is considered.
- Space Complexity: O(n) - The space for the visited array and the queue.
3. Union-Find
Intuition:
Union-Find efficiently tracks and merges disjoint sets, or connected components, which suits this problem perfectly. Initially, each city is its own province. As we process direct roads between cities, we union their sets. The number of unique roots in the Union-Find structure at the end will give us the number of provinces.
Code:
- Time Complexity: O(n^2): Iterate through the upper triangle of the matrix.
- Space Complexity: O(n): Additional space used by the Union-Find structure.