Problem
Given an n x n matrix isConnected, whereisConnected[i][j] = 1 means city i is directly connected to city j, return the number of provinces.
A province is a group of directly or indirectly connected cities. In other words, if one city can be reached from another through a chain of connections, they belong to the same province.
Example(s)
Consider the following examples to understand the expected input and output.Example 1
Input
isConnected =
[[1,1,0],
[1,1,0],
[0,0,1]]Output
2Example 2
Input
isConnected =
[[1,0,0],
[0,1,0],
[0,0,1]]Output
3Solution
This solution uses Depth-First Search (DFS) to find all connected cities. We maintain a visited array to track the cities that have already been explored.We iterate through every city. Whenever we find an unvisited city, it represents the start of a new province. We increment the province count and use DFS to visit all cities connected to it.
class Solution {
public int findCircleNum(int[][] isConnected) {
int provinces = 0;
int n = isConnected.length;
boolean[] visited = new boolean[n];
// Start DFS from every unvisited city.
// Each new DFS represents a new province.
for (int i = 0; i < n; i++) {
if (!visited[i]) {
provinces++;
dfs(i, isConnected, visited);
}
}
return provinces;
}
private void dfs(int i, int[][] isConnected, boolean[] visited) {
// Mark the current city as visited.
visited[i] = true;
// Get all connections of the current city.
int[] connected = isConnected[i];
// Visit every city directly connected to the current city.
for (int j = 0; j < isConnected.length; j++) {
if (connected[j] == 1 && !visited[j]) {
dfs(j, isConnected, visited);
}
}
}
}Complexity
For each city, we may scan all other cities in the adjacency matrix, so the time complexity isO(n2), where n is the number of cities.
The visited array and DFS recursion use
O(n) extra space.