Problem Statement

• LeetCode 547 Number of Provinces

LeetCode 547 asks us to find the number of provinces in a given network of cities. We're given an n x n adjacency matrix isConnected where isConnected[i][j] = 1 if the ith city and jth city are directly connected, and isConnected[i][j] = 0 otherwise. A province is a group of directly or indirectly connected cities with no other cities outside the group. We need to return the total number of provinces.

Algorithm Walkthrough

This problem is essentially asking us to find the number of connected components in an undirected graph. The solution uses Depth-First Search (DFS) to traverse each connected component:

1. Initialize tracking variables: Create a visited boolean array to track which cities we've already processed, and a count variable to store the number of provinces.

2. Iterate through all cities: For each city i from 0 to N-1:

   • If the city hasn't been visited yet, we've found a new province
   • Increment the province count
   • Use DFS to mark all cities in this province as visited

3. DFS traversal: The dfs method explores all cities connected to the current city:

   • For each adjacent city j (where M[i][j] != 0)
   • If city j hasn't been visited, mark it as visited and recursively call DFS on it
   • This ensures we visit all cities in the current connected component

4. Return result: After processing all cities, return the total count of provinces.

The key insight is that each time we encounter an unvisited city in the main loop, we've discovered a new province. The DFS ensures we mark all cities in that province as visited, so they won't be counted again.

Complexity Analysis

Time Complexity: O(N²)

• We iterate through each city once in the main loop: O(N)
• For each unvisited city, we perform DFS which in the worst case visits all other cities
• The DFS examines each edge in the adjacency matrix at most once across all calls
• Since we have an N×N matrix, this gives us O(N²) total time complexity

Space Complexity: O(N)

• The visited array takes O(N) space
• The recursion stack in DFS can go up to O(N) deep in the worst case (when all cities form a single chain)
• Total space complexity is O(N)

Full Solution (Java)

class Solution {
    public int findCircleNum(int[][] M) {
        int N = M.length;
        boolean[] visited = new boolean[N];
        int count = 0;

        for(int i = 0; i < N; i++){
            if(!visited[i]){
                count++;
                dfs(M, i, visited);
            }
        }
        return count;  
    }

    private void dfs(int[][] M, int i, boolean[] visited){
        for(int j = 0; j < M[i].length; j++){
            if(!visited[j] && M[i][j] != 0){
                visited[j] = true;
                dfs(M, j, visited);
            }
        }
    }
}

The solution elegantly handles the connected components problem by treating each unvisited city as the start of a new province and using DFS to explore all cities within that province. This ensures each city is counted exactly once and each province is identified correctly.