LeetCode 547: Number of Provinces

Explanation:

To solve this problem, we can use a depth-first search (DFS) algorithm to traverse the graph of cities and find all connected provinces. We will maintain a boolean array to mark visited cities and increment the count of provinces whenever we encounter a new unvisited city during the DFS traversal.

• Algorithm:

  1. Initialize a boolean array visited of size n to keep track of visited cities.
  2. Iterate through each city, and if a city is not visited, perform a DFS traversal starting from that city.
  3. In the DFS function, mark the current city as visited and recursively call the DFS function on its connected cities.
  4. Increment the province count whenever a new unvisited city is encountered in the DFS traversal.
  5. Return the total count of provinces.

• Time Complexity: O(n^2) where n is the number of cities.

• Space Complexity: O(n) for the boolean array and recursion stack.

:

class Solution {
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        boolean[] visited = new boolean[n];
        int provinces = 0;
        
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs(isConnected, visited, i);
                provinces++;
            }
        }
        
        return provinces;
    }
    
    private void dfs(int[][] isConnected, boolean[] visited, int city) {
        visited[city] = true;
        
        for (int j = 0; j < isConnected.length; j++) {
            if (isConnected[city][j] == 1 && !visited[j]) {
                dfs(isConnected, visited, j);
            }
        }
    }
}