Sponsored
Sponsored
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.
Time Complexity: O(n^2), as we may visit each cell in the matrix.
Space Complexity: O(n) for the visited array.
1class Solution {
2 public int findCircleNum(int[][] isConnected) {
3 int n = isConnected.length;
4 boolean[] visited = new boolean[n];
5 int provinces = 0;
6
7 for (int i = 0; i < n; i++) {
8 if (!visited[i]) {
9 dfs(isConnected, visited, i);
10 provinces++;
11 }
12 }
13 return provinces;
14 }
15
16 private void dfs(int[][] isConnected, boolean[] visited, int node) {
17 visited[node] = true;
18 for (int i = 0; i < isConnected.length; i++) {
19 if (isConnected[node][i] == 1 && !visited[i]) {
20 dfs(isConnected, visited, i);
21 }
22 }
23 }
24}The Java solution implements DFS similarly by using a boolean array for visited cities. Each city starts a DFS call to mark all reachable cities if it hasn't been visited. Each fresh DFS initiation adds to the province count, representing a newly discovered province.
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).
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.
1
The Union-Find pattern in Python involves creating groups and minimizing tree depth by union by rank. The final province count is derived by checking how many root nodes exist within the parent array.