Number of Provinces

Number of Provinces Problem

Imagine a group of cities connected by direct roads. A province is defined as a group of directly or indirectly connected cities. The challenge is to find out how many such groups exist. This is exactly what the Number of Provinces problem in graph theory addresses.

This tutorial breaks down the problem from scratch and guides you through various algorithmic solutions using graph traversal, depth-first search, breadth-first search, and the Union-Find algorithm (also known as disjoint sets). Whether you're learning about network connectivity, solving islands counting problems, or simply strengthening your foundations in graphs, this guide covers it all.

Let’s answer common questions like:

• What are provinces in graph theory?
• How do we use DFS or BFS to count connected components?
• Is Union-Find faster than traversal-based methods?

Problem Explanation

You're given a square adjacency matrix where matrix[i][j] = 1 means city i and city j are directly connected. Your goal is to return the total number of connected components (or provinces) in this undirected graph.

Example:

1
2
3
4
5
isConnected = [
    [1, 1, 0],
    [1, 1, 0],
    [0, 0, 1]
]

Here, cities 0 and 1 are connected, and city 2 is alone. So, there are 2 provinces.

Graph Concepts Behind Province Counting

To solve the problem, you need to understand:

• Each city is a node.
• A direct connection is an edge.
• A province is a connected component.
• The task is to count how many connected components exist in the graph.

Now let’s look at different ways to achieve this.

Depth-First Search (DFS) to Count Provinces

How DFS Works in Graph Traversal

DFS is a graph traversal algorithm that starts from a node and visits all its connected neighbors recursively. In the Number of Provinces context, each time you initiate a DFS on an unvisited node, you’ve found a new province.

DFS Implementation with Adjacency Matrix

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def findCircleNum(isConnected):
    def dfs(city):
        for neighbor, connected in enumerate(isConnected[city]):
            if connected and neighbor not in visited:
                visited.add(neighbor)
                dfs(neighbor)

    visited = set()
    count = 0
    for city in range(len(isConnected)):
        if city not in visited:
            dfs(city)
            count += 1
    return count

Why DFS Works

• Efficiently visits all cities in a province.
• Every disconnected cluster is detected.
• Simple to implement with an adjacency matrix.

Breadth-First Search (BFS) to Count Connected Components

BFS Strategy for Province Identification

BFS explores the graph level by level using a queue. Each time you start BFS from an unvisited node, you discover a new connected component.

BFS Code Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from collections import deque

def findCircleNum(isConnected):
    visited = set()
    count = 0

    for city in range(len(isConnected)):
        if city not in visited:
            queue = deque([city])
            while queue:
                current = queue.popleft()
                for neighbor, connected in enumerate(isConnected[current]):
                    if connected and neighbor not in visited:
                        visited.add(neighbor)
                        queue.append(neighbor)
            count += 1
    return count

When to Use BFS

• Prefer BFS when recursion depth might be an issue.
• Performs well with dense connectivity.
• Clean separation of levels in network connectivity analysis.

Union-Find Algorithm (Disjoint Sets) for Counting Provinces

What is Union-Find?

The Union-Find algorithm, also known as disjoint sets, is ideal for quickly merging and checking connectivity between nodes. It's an efficient way to solve islands counting and province detection problems.

Union-Find Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def findCircleNum(isConnected):
    parent = list(range(len(isConnected)))

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    def union(x, y):
        rootX = find(x)
        rootY = find(y)
        if rootX != rootY:
            parent[rootY] = rootX

    for i in range(len(isConnected)):
        for j in range(i + 1, len(isConnected)):
            if isConnected[i][j]:
                union(i, j)

    return sum(parent[i] == i for i in range(len(isConnected)))

Advantages of Union-Find

• Excellent performance for large graphs.
• Avoids repeated graph traversal.
• Tracks connected components dynamically.

Adjacency Matrix vs. Adjacency List

• Adjacency matrix is perfect for small or dense graphs and is typically used in this problem.
• Adjacency list is more memory-efficient and better for sparse graphs, though it requires conversion in this context.

Want to optimize for larger datasets? Convert the matrix to an adjacency list and use DFS or BFS accordingly.

Conclusion

The Number of Provinces problem is a classic case of applying graph traversal to identify connected components. Depending on your needs, you can solve it with:

• DFS – intuitive and recursive.
• BFS – level-by-level and memory safe.
• Union-Find – lightning fast with disjoint sets.

Understand how cities are connected via the adjacency matrix, and applying the right strategy based on network connectivity, will make this problem straightforward to solve—and a powerful foundation for more advanced graph theory problems.