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.
1public class Solution {
2 public int FindCircleNum(int[][] isConnected) {
3 int n = isConnected.Length;
4 bool[] visited = new bool[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, bool[] 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}This C# solution uses DFS in the same strategy as the other languages. An array for keeping visited status is maintained, and DFS is executed from every unvisited city to discover all its connected components, thereby determining the provinces.
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 private int[] parent;
private int[] rank;
public UnionFind(int size) {
parent = new int[size];
rank = new int[size];
for (int i = 0; i < size; i++) {
parent[i] = i;
}
}
public int Find(int x) {
if (parent[x] != x) {
parent[x] = Find(parent[x]);
}
return parent[x];
}
public void Union(int x, int y) {
int rootX = Find(x);
int rootY = Find(y);
if (rootX != rootY) {
if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
}
}
public class Solution {
public int FindCircleNum(int[][] isConnected) {
int n = isConnected.Length;
UnionFind uf = new UnionFind(n);
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (isConnected[i][j] == 1) {
uf.Union(i, j);
}
}
}
int provinces = 0;
for (int i = 0; i < n; i++) {
if (uf.Find(i) == i) {
provinces++;
}
}
return provinces;
}
}The C# solution involves employing a Union-Find data structure, useful for dynamically finding and merging disjoint sets. Provinces are calculated by counting distinct roots after all unions.