LeetCode 547: Number of Provinces Solution in Python – A Step-by-Step Guide

What Is LeetCode 547: Number of Provinces?

In LeetCode 547: Number of Provinces, you’re given an n x n adjacency matrix isConnected where isConnected[i][j] = 1 means cities i and j are directly connected, and 0 means they’re not, and your task is to return the number of provinces—disconnected groups of cities. For example, with isConnected = [[1,1,0],[1,1,0],[0,0,1]], there are 2 provinces: cities 0 and 1 are connected, and city 2 is separate. This problem builds on LeetCode 200: Number of Islands for graph component counting but uses an adjacency matrix representation.

Problem Statement

• Input: isConnected (List[List[int]])—n x n adjacency matrix of 0s and 1s.
• Output: Integer—number of provinces (connected components).
• Rules: isConnected[i][j] = 1 means direct connection; count distinct groups.

Constraints

• 1 <= n <= 200
• isConnected[i][j] is 0 or 1.
• isConnected[i][i] = 1 (self-connection).
• isConnected[i][j] == isConnected[j][i] (symmetric).

Examples

• Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]]
• Output: 2
• Cities 0 and 1 connected, city 2 separate.
• Input: isConnected = [[1,0,0],[0,1,0],[0,0,1]]
• Output: 3
• Each city isolated.
• Input: isConnected = [[1,1,1],[1,1,1],[1,1,1]]
• Output: 1
• All cities connected.

Understanding the Problem: Counting Provinces

To solve LeetCode 547: Number of Provinces in Python, we need to count the number of connected components in a graph represented by an adjacency matrix, where isConnected[i][j] = 1 indicates a direct edge between cities i and j. A naive approach might check all pairs (O(n²)), but with up to 200 cities, we can optimize using graph traversal to mark connected groups efficiently. Each province is a set of cities reachable from one another, directly or indirectly. We’ll explore:

• Best Solution (DFS with Visited Tracking): O(n²) time, O(n) space—intuitive and efficient.
• Alternative Solution (Union-Find with Disjoint Set): O(n² * α(n)) time, O(n) space—powerful but complex.

Let’s dive into the DFS solution with a friendly breakdown!

Best Solution: DFS with Visited Tracking

Why DFS Wins

The DFS with visited tracking is the best for LeetCode 547 because it efficiently counts provinces in O(n²) time and O(n) space by traversing the graph from each unvisited city, marking all connected cities in a single depth-first search, and incrementing a counter for each new component. It’s like exploring a map, coloring each connected region as you go, with a simple, clear approach!

How It Works

Think of this as a province-mapping adventure:

• Step 1: Initialize Visited Set:
• Track visited cities to avoid recounting.
• Step 2: DFS Traversal:
• From an unvisited city, explore all directly connected cities (1s in row).
• Mark each as visited, recurse to their connections.
• Step 3: Count Provinces:
• Each new unvisited city starts a new province; increment counter.
• Step 4: Return Count:
• Total number of provinces found.
• Why It Works:
• DFS exhaustively marks each component in one pass per province.
• Visited set ensures no overlap.

It’s like a graph-province explorer!

Step-by-Step Example

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

• Init: visited = set(), provinces = 0, n = 3.
• Step 1: Start at city 0 (unvisited):
• DFS(0): isConnected[0] = [1,1,0], visit 0, 1.
• DFS(1): isConnected[1] = [1,1,0], 0 and 1 already visited, skip.
• visited = {0, 1}, provinces = 1.
• Step 2: Next unvisited, city 2:
• DFS(2): isConnected[2] = [0,0,1], visit 2.
• visited = {0, 1, 2}, provinces = 2.
• Step 3: All visited, stop.
• Result: 2.

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

• Step 1: DFS(0): Visit 0, provinces = 1.
• Step 2: DFS(1): Visit 1, provinces = 2.
• Step 3: DFS(2): Visit 2, provinces = 3.
• Result: 3.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained for beginners:

Copy codeclass Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        if not isConnected:
            return 0

        # Step 1: Initialize visited set and provinces
        n = len(isConnected)
        visited = set()
        provinces = 0

        # Step 2: DFS helper to mark connected cities
        def dfs(city):
            visited.add(city)
            for neighbor in range(n):
                if isConnected[city][neighbor] == 1 and neighbor not in visited:
                    dfs(neighbor)

        # Step 3: Count provinces
        for city in range(n):
            if city not in visited:
                dfs(city)
                provinces += 1

        # Step 4: Return total provinces
        return provinces

• Lines 4-5: Handle empty input.
• Lines 8-10: Set up visited set and counter.
• Lines 13-17: DFS: Mark city visited, explore unvisited neighbors with 1s.
• Lines 20-23: Iterate cities, start DFS for unvisited, increment provinces.
• Line 26: Return count.
• Time Complexity: O(n²)—visit each city and check all neighbors.
• Space Complexity: O(n)—visited set.

It’s like a province-counting cartographer!

Alternative Solution: Union-Find with Disjoint Set

Why an Alternative Approach?

The Union-Find with disjoint set solution uses a data structure to track connected components, merging sets as connections are found, running in O(n² * α(n)) time (near-linear with inverse Ackermann function) and O(n) space. It’s powerful for graph problems but less intuitive, making it a great alternative for Union-Find learners or when connectivity merging is preferred.

How It Works

Picture this as a province-merging diplomat:

• Step 1: Initialize disjoint set with each city in its own set.
• Step 2: Union connected cities based on matrix.
• Step 3: Count distinct sets (provinces).
• Step 4: Return count.

It’s like a province-unifying negotiator!

Step-by-Step Example

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

• Init: Parent = [0, 1, 2], rank = [0, 0, 0], provinces = 3.
• Step 1: Union:
• (0,1): Union(0,1), Parent = [0, 0, 2], provinces = 2.
• (1,0): Already unioned, skip.
• Step 2: No more unions (0-2, 1-2 are 0).
• Result: 2.

Code for Union-Find Approach

Copy codeclass Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        n = len(isConnected)

        # Step 1: Initialize disjoint set
        parent = list(range(n))
        rank = [0] * n
        provinces = n

        # Step 2: Find and Union functions
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])  # Path compression
            return parent[x]

        def union(x, y):
            nonlocal provinces
            px, py = find(x), find(y)
            if px == py:
                return
            if rank[px] < rank[py]:
                px, py = py, px
            parent[py] = px
            if rank[px] == rank[py]:
                rank[px] += 1
            provinces -= 1

        # Step 3: Process connections
        for i in range(n):
            for j in range(i + 1, n):
                if isConnected[i][j] == 1:
                    union(i, j)

        # Step 4: Return province count
        return provinces

• Lines 5-8: Initialize parent (self), rank, and count.
• Lines 11-14: Find with path compression.
• Lines 17-25: Union with rank optimization.
• Lines 28-31: Merge connected cities.
• Line 34: Return final count.
• Time Complexity: O(n² * α(n))—near-linear with Union-Find.
• Space Complexity: O(n)—parent and rank arrays.

It’s a Union-Find province counter!

Comparing the Two Solutions

• DFS (Best):
• Pros: O(n²), O(n), intuitive.
• Cons: Stack space.
• Union-Find (Alternative):
• Pros: O(n² * α(n)), O(n), scalable.
• Cons: Complex logic.

DFS wins for simplicity!

Additional Examples and Edge Cases

• [[1]]: 1.
• [[1,0],[0,1]]: 2.
• [[1,1],[1,1]]: 1.

DFS handles them all!

Complexity Recap

• DFS: Time O(n²), Space O(n).
• Union-Find: Time O(n² * α(n)), Space O(n).

DFS’s the clarity champ!

Key Takeaways

• DFS: Traversal ease—learn at Python Basics!
• Union-Find: Set power.
• Graphs: Provinces are fun.
• Python: DFS or UF, your pick!

Final Thoughts: Count Those Provinces!

LeetCode 547: Number of Provinces in Python is a delightful graph challenge. DFS with visited tracking is your fast track, while Union-Find offers a powerful twist. Want more? Try LeetCode 200: Number of Islands or LeetCode 684: Redundant Connection. Ready to explore? Head to Solve LeetCode 547 on LeetCode and map those provinces today!