[Medium] 547. Number of Provinces

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.

Examples

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 <= 200
  • n == isConnected.length
  • n == isConnected[i].length
  • isConnected[i][j] is 1 or 0.
  • isConnected[i][i] == 1
  • isConnected[i][j] == isConnected[j][i]

Clarification Questions

Before diving into the solution, here are 5 important clarifications and assumptions to discuss during an interview:

  1. Province definition: What is a province? (Assumption: Group of directly or indirectly connected cities - connected component)

  2. Connection matrix: How is connectivity represented? (Assumption: isConnected[i][j] = 1 means cities i and j are directly connected)

  3. Return value: What should we return? (Assumption: Integer - number of provinces (connected components))

  4. Self-connection: Are cities connected to themselves? (Assumption: Yes - isConnected[i][i] = 1 per constraints)

  5. Transitivity: Is connection transitive? (Assumption: Yes - if A connects to B and B connects to C, then A connects to C)

Interview Deduction Process (20 minutes)

Step 1: Brute-Force Approach (5 minutes)

For each city, check all other cities to see if they’re connected directly or indirectly. Use a visited array and for each unvisited city, perform DFS/BFS to mark all connected cities. Count how many times we need to start a new DFS/BFS (each represents a province). This approach works but requires careful tracking of visited cities and may have redundant checks.

Step 2: Semi-Optimized Approach (7 minutes)

Use DFS: for each unvisited city, perform DFS to mark all cities in its province as visited. Count the number of DFS calls (each represents one province). This avoids redundant checks by using a visited array. Time complexity is O(n²) where n is the number of cities, as we may check all connections. This works well but can be optimized with Union-Find for better average performance.

Step 3: Optimized Solution (8 minutes)

Use Union-Find (Disjoint Set Union) to group connected cities. For each connection in the matrix, union the two cities. After processing all connections, count the number of distinct roots (each root represents a province). Union-Find achieves O(n² × α(n)) time where α is the inverse Ackermann function (effectively constant), making it very efficient. Alternatively, DFS/BFS also works in O(n²) time. The key insight is that provinces are connected components, and Union-Find naturally groups them efficiently, especially when we need to process connections incrementally.

Solution 1: Union-Find (Disjoint Set Union) - Recommended

Time Complexity: O(n² × α(n)) where α is the inverse Ackermann function
Space Complexity: O(n) - For parent array

This solution uses Union-Find to group connected cities into provinces.

class Solution {
private:
    int find(vector<int>& parent, int index) {
        if(parent[index] != index) {
            parent[index] = find(parent, parent[index]);
        }
        return parent[index];
    }

    void unite(vector<int>& parent, int index1, int index2) {
        parent[find(parent, index1)] = find(parent, index2);
    }
    
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        int cnt = isConnected.size();
        vector<int> parent(cnt);
        
        // Initialize: each city is its own parent
        for(int i = 0; i < cnt; i++) {
            parent[i] = i;
        }
        
        // Union connected cities
        for(int i = 0; i < cnt; i++) {
            for(int j = 0; j < cnt; j++) {
                if(isConnected[i][j] == 1) {
                    unite(parent, i, j);
                }
            }
        }
        
        // Count provinces (number of roots)
        int circles = 0;
        for(int i = 0; i < cnt; i++) {
            if(parent[i] == i) circles++;
        }
        return circles;
    }
};

How Solution 1 Works

  1. Initialization: Each city starts as its own parent (separate province)
  2. Union Operation: For each connection isConnected[i][j] == 1, unite cities i and j
  3. Path Compression: The find function compresses paths for efficiency
  4. Count Provinces: Count the number of roots (cities where parent[i] == i)

Key Insight

A province is a connected component. Union-Find groups all connected cities under the same root, so counting roots gives the number of provinces.

Time Complexity: O(n²) - Visit each city once
Space Complexity: O(n) - For visited array and recursion stack

Use DFS to explore all cities in a province.

class Solution {
private:
    void dfs(vector<vector<int>>& isConnected, vector<bool>& visited, int city) {
        visited[city] = true;
        for(int j = 0; j < isConnected.size(); j++) {
            if(isConnected[city][j] == 1 && !visited[j]) {
                dfs(isConnected, visited, j);
            }
        }
    }
    
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        int n = isConnected.size();
        vector<bool> visited(n, false);
        int provinces = 0;
        
        for(int i = 0; i < n; i++) {
            if(!visited[i]) {
                dfs(isConnected, visited, i);
                provinces++;
            }
        }
        
        return provinces;
    }
};

How Solution 2 Works

  1. Visit each city: Iterate through all cities
  2. DFS exploration: For each unvisited city, start DFS to mark all connected cities
  3. Count provinces: Each DFS call represents one province

Time Complexity: O(n²)
Space Complexity: O(n)

Use BFS instead of DFS for iterative exploration.

class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        int n = isConnected.size();
        vector<bool> visited(n, false);
        int provinces = 0;
        
        for(int i = 0; i < n; i++) {
            if(!visited[i]) {
                queue<int> q;
                q.push(i);
                visited[i] = true;
                
                while(!q.empty()) {
                    int city = q.front();
                    q.pop();
                    
                    for(int j = 0; j < n; j++) {
                        if(isConnected[city][j] == 1 && !visited[j]) {
                            visited[j] = true;
                            q.push(j);
                        }
                    }
                }
                
                provinces++;
            }
        }
        
        return provinces;
    }
};

Comparison of Approaches

Aspect Union-Find DFS BFS
Time Complexity O(n² × α(n)) O(n²) O(n²)
Space Complexity O(n) O(n) O(n)
Code Simplicity Moderate Simple Moderate
Best For Dynamic connectivity Static graph Static graph

Example Walkthrough

Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]]

Solution 1 (Union-Find):

Initial: parent = [0, 1, 2]

Process connections:
i=0, j=0: isConnected[0][0] = 1 → unite(0, 0) → no change
i=0, j=1: isConnected[0][1] = 1 → unite(0, 1)
  find(0) = 0, find(1) = 1
  parent[0] = 1
  parent = [1, 1, 2]

i=1, j=0: isConnected[1][0] = 1 → unite(1, 0)
  find(1) = 1, find(0) = find(1) = 1
  Already connected, no change

i=1, j=1: isConnected[1][1] = 1 → unite(1, 1) → no change

i=2, j=2: isConnected[2][2] = 1 → unite(2, 2) → no change

Final: parent = [1, 1, 2]
Count roots: parent[1] == 1, parent[2] == 2
Result: 2 provinces

Solution 2 (DFS):

visited = [false, false, false]

i=0: Not visited
  DFS(0):
    Mark 0 as visited
    Check j=0: isConnected[0][0]=1, visited[0]=true, skip
    Check j=1: isConnected[0][1]=1, visited[1]=false
      DFS(1):
        Mark 1 as visited
        Check j=0: visited[0]=true, skip
        Check j=1: visited[1]=true, skip
        Check j=2: isConnected[1][2]=0, skip
    Check j=2: isConnected[0][2]=0, skip
  provinces = 1

i=1: Already visited, skip
i=2: Not visited
  DFS(2):
    Mark 2 as visited
    Check j=0: isConnected[2][0]=0, skip
    Check j=1: isConnected[2][1]=0, skip
    Check j=2: visited[2]=true, skip
  provinces = 2

Result: 2 provinces

Complexity Analysis

Solution Time Space Notes
Union-Find O(n² × α(n)) O(n) Path compression makes α(n) ≈ constant
DFS O(n²) O(n) Simple and intuitive
BFS O(n²) O(n) Iterative, no recursion

Edge Cases

  1. Single city: [[1]] → return 1
  2. All connected: All cities in one province → return 1
  3. None connected: Each city is separate → return n
  4. Self-loops: isConnected[i][i] == 1 (handled automatically)

Common Mistakes

  1. Not using path compression: Leads to O(n) find operations
  2. Wrong root counting: Counting parent[i] == i before path compression
  3. Symmetric matrix: Only need to check upper or lower triangle (but checking all is fine)
  4. Visited array: In DFS/BFS, forgetting to mark visited

Key Insights

  1. Connected Components: Provinces are connected components in the graph
  2. Symmetric Matrix: isConnected[i][j] == isConnected[j][i] (undirected graph)
  3. Self-loops: isConnected[i][i] == 1 (each city connects to itself)
  4. Union-Find Efficiency: Path compression makes find operations nearly O(1)

Optimization Tips

  1. Path Compression: Essential for Union-Find efficiency
  2. Union by Rank: Can add rank optimization for better performance
  3. Early Exit: Can optimize by only checking upper triangle (but code is simpler checking all)

Pattern Recognition

This problem demonstrates the “Connected Components” pattern:

1. Use Union-Find or DFS/BFS to group connected nodes
2. Count the number of distinct groups
3. Each group represents one component

Similar problems:

  • Number of Islands
  • Max Area of Island
  • Friend Circles (same problem)
  • Accounts Merge