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.
1#include <stdbool.h>
2
3void dfs(int n, int node, int isConnected[n][n], bool visited[n]) {
4 visited[node] = true;
5 for (int i = 0; i < n; i++) {
6 if (isConnected[node][i] == 1 && !visited[i]) {
7 dfs(n, i, isConnected, visited);
8 }
9 }
10}
11
12int findCircleNum(int isConnected[200][200], int n) {
13 bool visited[n];
14 for (int i = 0; i < n; i++) visited[i] = false;
15 int provinces = 0;
16 for (int i = 0; i < n; i++) {
17 if (!visited[i]) {
18 dfs(n, i, isConnected, visited);
19 provinces++;
20 }
21 }
22 return provinces;
23}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.
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
This Java solution features a Union-Find class with union and find operations. Upon establishing connections, cities are grouped under unique leaders using union sets and path compression. Provinces correspond to the count of unique root nodes.