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]#547 Number of Provinces is a classic graph connectivity problem where cities are represented in an adjacency matrix. The goal is to determine how many disconnected groups (or provinces) exist. Each province is essentially a connected component in an undirected graph.
A common strategy is to treat the matrix as a graph and explore connections using Depth-First Search (DFS) or Breadth-First Search (BFS). Starting from an unvisited city, you traverse all directly and indirectly connected cities, marking them as visited. Each time you start a new traversal from an unvisited city, you discover a new province.
Another efficient approach is Union-Find (Disjoint Set). By unioning connected cities and tracking parent sets, you can determine how many independent groups remain. This method is especially useful for dynamic connectivity problems.
Since the input is an n x n matrix, most approaches iterate through all possible city pairs, leading to O(n²) time complexity with additional space for visited tracking or disjoint sets.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| DFS / BFS Traversal | O(n^2) | O(n) |
| Union-Find (Disjoint Set) | O(n^2) | O(n) |
take U forward
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 }
private void Dfs(int[][] isConnected, bool[] visited, int node) {
visited[node] = true;
for (int i = 0; i < isConnected.Length; i++) {
if (isConnected[node][i] == 1 && !visited[i]) {
Dfs(isConnected, visited, i);
}
}
}
}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;
}
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of this problem frequently appear in FAANG and other top tech company interviews. It tests core graph concepts such as connected components, traversal techniques, and Union-Find.
The optimal approach is to treat the matrix as a graph and count connected components using DFS or BFS. Another efficient option is Union-Find, which groups connected cities and counts the number of disjoint sets remaining.
Graphs are the key concept behind this problem. You typically use a visited array with DFS/BFS or a Disjoint Set (Union-Find) data structure to efficiently track connected components.
The adjacency matrix directly represents whether two cities are connected. This format allows you to easily check relationships between every pair of cities while traversing the graph.
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.