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] is 1 or 0.isConnected[i][i] == 1isConnected[i][j] == isConnected[j][i]This approach uses Depth-First Search (DFS) to count the number of provinces. The core idea is to treat the connected cities as a graph and perform a DFS traversal starting from each city. During traversal, mark all reachable cities from the starting city. Each starting city for a DFS that visits new cities indicates the discovery of a new province.
The objective is to find connected components in the graph, which represent provinces. We declare a boolean array visited to track visited cities. We implement a helper function dfs to perform DFS traversal from each unvisited node, marking all reachable nodes. Each DFS starting from an unvisited node suggests a new province has been found.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2), as we may visit each cell in the matrix.
Space Complexity: O(n) for the visited array.
This approach employs the Union-Find (Disjoint Set Union) algorithm to find the number of provinces. This algorithm efficiently handles dynamic connectivity queries. By iteratively checking connections and performing unions, we can identify distinct connected components (provinces).
The Union-Find approach involves two primary operations: 'find' and 'union'. Each city starts as its own component, and each connection adds to the union. The find method returns the root ancestor for any node, which helps in determining connected components. The total provinces are the count of unique roots in the parent array.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2 * α(n)), where α is the inverse Ackermann function representing nearly constant time for union-find operations.
Space Complexity: O(n), the space for parent and rank arrays.
| Approach | Complexity |
|---|---|
| Approach 1: Depth-First Search (DFS) | Time Complexity: O(n^2), as we may visit each cell in the matrix. |
| Approach 2: Union-Find | Time Complexity: O(n^2 * α(n)), where α is the inverse Ackermann function representing nearly constant time for union-find operations. |
G-7. Number of Provinces | C++ | Java | Connected Components • take U forward • 373,269 views views
Watch 9 more video solutions →Practice Number of Provinces with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor