# LeetCode 547: Number of Provinces

## Problem Restatement

We are given an `n x n` matrix called `isConnected`.

There are `n` cities.

If:

```python
isConnected[i][j] == 1
```

then city `i` and city `j` are directly connected.

A province is a group of cities that are directly or indirectly connected to each other, with no city outside the group connected to them.

We need to return the number of provinces.

This is the same as counting connected components in an undirected graph represented by an adjacency matrix. A province may contain cities connected through intermediate cities, not only direct neighbors.

## Input and Output

| Item | Meaning |
|---|---|
| Input | An `n x n` matrix `isConnected` |
| Output | Number of provinces |
| Matrix value `1` | Cities are connected |
| Matrix value `0` | Cities are not directly connected |
| Graph type | Undirected graph |
| Goal | Count connected components |

Function shape:

```python
def findCircleNum(isConnected: list[list[int]]) -> int:
    ...
```

## Examples

Consider:

```python
isConnected = [
    [1, 1, 0],
    [1, 1, 0],
    [0, 0, 1],
]
```

City `0` is connected to city `1`.

City `2` is isolated.

So there are two provinces:

```text
{0, 1}
{2}
```

The answer is:

```python
2
```

Another example:

```python
isConnected = [
    [1, 0, 0],
    [0, 1, 0],
    [0, 0, 1],
]
```

No city is connected to any other city.

Each city is its own province:

```text
{0}
{1}
{2}
```

The answer is:

```python
3
```

## First Thought: Treat the Matrix as a Graph

The matrix is an adjacency matrix.

Each city is a node.

Each `1` between two different cities means there is an edge between them.

So the problem becomes:

```text
How many connected components are in this graph?
```

To count connected components, we can use DFS, BFS, or Union Find.

The DFS version is the most direct.

## Key Insight

If we start DFS from one unvisited city, DFS will visit every city in that same province.

So each time we find an unvisited city and start a new DFS, we have discovered one new province.

The algorithm is:

```text
number of DFS starts = number of provinces
```

This works because cities in the same province are all reachable from each other through direct or indirect connections.

## Algorithm

Create a boolean array:

```python
visited = [False] * n
```

Then scan every city.

For each city `i`:

1. If `i` is already visited, skip it.
2. If `i` is not visited:
   1. Start DFS from `i`.
   2. Mark every reachable city as visited.
   3. Increase the province count by `1`.

The DFS checks every possible neighbor `j`.

If:

```python
isConnected[i][j] == 1
```

and city `j` has not been visited, then city `j` belongs to the same province.

## Correctness

Each DFS starts from an unvisited city.

When DFS starts from city `i`, it follows all direct connections from `i`, then all direct connections from those cities, and so on. Therefore, it visits exactly the cities that are directly or indirectly connected to `i`.

Those cities form one province.

After this DFS finishes, every city in that province is marked visited. So none of them can start another DFS later.

If the main loop later finds another unvisited city, that city cannot belong to any previously counted province. If it did, it would have been reached and marked visited during that province's DFS. Therefore, starting DFS from it counts a new province.

Thus, the algorithm counts every province once and only once.

## Complexity

Let `n` be the number of cities.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n^2)` | For each city, DFS may scan a full row of the adjacency matrix |
| Space | `O(n)` | The visited array and recursion stack |

The matrix itself is input space and is not counted as extra space.

## Implementation

```python
class Solution:
    def findCircleNum(self, isConnected: list[list[int]]) -> int:
        n = len(isConnected)
        visited = [False] * n

        def dfs(city: int) -> None:
            visited[city] = True

            for neighbor in range(n):
                if isConnected[city][neighbor] == 1 and not visited[neighbor]:
                    dfs(neighbor)

        provinces = 0

        for city in range(n):
            if not visited[city]:
                provinces += 1
                dfs(city)

        return provinces
```

## Code Explanation

We read the number of cities:

```python
n = len(isConnected)
```

Then we create the visited array:

```python
visited = [False] * n
```

The DFS marks the current city:

```python
visited[city] = True
```

Then it scans all possible cities:

```python
for neighbor in range(n):
```

If the neighbor is connected and unvisited:

```python
if isConnected[city][neighbor] == 1 and not visited[neighbor]:
```

we continue DFS into that neighbor.

The main loop counts provinces:

```python
if not visited[city]:
    provinces += 1
    dfs(city)
```

Each time this branch runs, we have found a new connected component.

## BFS Version

DFS and BFS solve the same connectivity problem.

```python
from collections import deque

class Solution:
    def findCircleNum(self, isConnected: list[list[int]]) -> int:
        n = len(isConnected)
        visited = [False] * n
        provinces = 0

        for start in range(n):
            if visited[start]:
                continue

            provinces += 1
            visited[start] = True
            queue = deque([start])

            while queue:
                city = queue.popleft()

                for neighbor in range(n):
                    if isConnected[city][neighbor] == 1 and not visited[neighbor]:
                        visited[neighbor] = True
                        queue.append(neighbor)

        return provinces
```

This version avoids recursion depth concerns.

## Union Find Version

Union Find is also natural because each `1` means two cities belong to the same component.

```python
class Solution:
    def findCircleNum(self, isConnected: list[list[int]]) -> int:
        n = len(isConnected)
        parent = list(range(n))
        rank = [0] * n

        def find(x: int) -> int:
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]

        def union(a: int, b: int) -> bool:
            root_a = find(a)
            root_b = find(b)

            if root_a == root_b:
                return False

            if rank[root_a] < rank[root_b]:
                parent[root_a] = root_b
            elif rank[root_a] > rank[root_b]:
                parent[root_b] = root_a
            else:
                parent[root_b] = root_a
                rank[root_a] += 1

            return True

        provinces = n

        for i in range(n):
            for j in range(i + 1, n):
                if isConnected[i][j] == 1:
                    if union(i, j):
                        provinces -= 1

        return provinces
```

We start with `n` separate provinces.

Every successful union merges two provinces, so we subtract `1`.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.findCircleNum([
        [1, 1, 0],
        [1, 1, 0],
        [0, 0, 1],
    ]) == 2

    assert s.findCircleNum([
        [1, 0, 0],
        [0, 1, 0],
        [0, 0, 1],
    ]) == 3

    assert s.findCircleNum([
        [1, 1, 0],
        [1, 1, 1],
        [0, 1, 1],
    ]) == 1

    assert s.findCircleNum([
        [1],
    ]) == 1

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| Two connected cities and one isolated | Checks multiple provinces |
| No inter-city connections | Every city is its own province |
| Indirect connection | Checks transitive connectivity |
| Single city | Minimum input |