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]

Thinking Process

  1. Connected Components: Provinces are connected components in the graph
  • Model entities as nodes and relationships as edges.
  • Pick traversal (BFS/DFS) or shortest-path (Dijkstra) based on weights.
  • Union-Find helps when connectivity updates are frequent.
Graph BFS layers S a b t BFS: expand by layers (queue)

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Recursive DFS (this problem) O(n) O(h) stack Natural for trees and graphs
Iterative DFS (stack) O(n) O(n) Avoid recursion depth limits
DFS with memoization O(n) O(n) Overlapping subproblems on graphs
Backtracking DFS O(2^n) typical O(n) Enumerate choices with pruning

Solution

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:
    def find(self, parent, x):
        if parent[x] != x:
            parent[x] = self.find(parent, parent[x])
        return parent[x]

    def unite(self, parent, x, y):
        rootX = self.find(parent, x)
        rootY = self.find(parent, y)
        parent[rootX] = rootY

    def findCircleNum(self, isConnected):
        n = len(isConnected)

        parent = list(range(n))

        # Union all connected cities
        for i in range(n):
            for j in range(n):
                if isConnected[i][j] == 1:
                    self.unite(parent, i, j)

        # Count roots
        circles = 0
        for i in range(n):
            if self.find(parent, i) == i:
                circles += 1

        return circles

Solution Explanation

Approach: Recursive DFS (this problem)

Key idea: 1. Connected Components: Provinces are connected components in the graph

How the code works:

  1. Connected Components: Provinces are connected components in the graph
    • Model entities as nodes and relationships as edges.
    • Pick traversal (BFS/DFS) or shortest-path (Dijkstra) based on weights.
    • Union-Find helps when connectivity updates are frequent.

Walkthrough — input isConnected = [[1,1,0],[1,1,0],[0,0,1]], expected output 2:

  1. Initialize variables from the problem setup.
  2. Apply the main loop / recursion until the condition is met.
  3. Confirm the result matches the expected output.
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

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.

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

| 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 |

Common Mistakes

  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)

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

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:

Key Takeaways

  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)