# Number of Provinces
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/number-of-provinces)
Canonical: https://scaleengineer.com/dsa/problems/number-of-provinces
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search), [Union Find](https://scaleengineer.com/algorithms/union-find)
**Data structures:** Graph
**Companies:** [DoorDash](https://scaleengineer.com/companies/doordash), [Sprinklr](https://scaleengineer.com/companies/sprinklr), [Two Sigma](https://scaleengineer.com/companies/two-sigma)
---
## Problem
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**_.

**Example 1:**

![](https://assets.glich.co/dsa/number-of-provinces/image0.jpg) 

**Input:** isConnected = [[1,1,0],[1,1,0],[0,0,1]]
**Output:** 2

**Example 2:**

![](https://assets.glich.co/dsa/number-of-provinces/image1.jpg) 

**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]`

# Approaches
## Disjoint Set Union (Union-Find)
The Union-Find data structure, also known as Disjoint Set Union (DSU), is highly efficient for problems that involve partitioning a set of elements into a number of disjoint, non-overlapping subsets. This problem fits perfectly, as a province is a set of connected cities. We can treat each city as an element. If two cities are connected, we merge their sets. The final number of disjoint sets gives us the number of provinces.
**Time:** O(n^2 * α(n)) - We iterate through the `n x n` matrix, which takes O(n^2) time. Each `union` operation takes nearly constant time, O(α(n)), where α(n) is the inverse Ackermann function. The total time is dominated by the matrix traversal. · **Space:** O(n) - We need a `parent` array and a `rank` array, both of size `n`.
**Pros:** Extremely efficient and a standard tool for connectivity problems.; The Union-Find data structure is versatile and applicable to a wide range of other problems (e.g., Kruskal's algorithm, cycle detection).
**Cons:** The implementation is more complex compared to a standard graph traversal like DFS or BFS.; The time complexity has an extra `α(n)` factor, making it slightly slower in theory than a pure O(n^2) traversal for an adjacency matrix representation, although this factor is negligible in practice.
### Explanation
We initialize a DSU data structure for `n` cities, where each city is initially in its own set. This means we start with `n` provinces. We use a `parent` array to track the representative of each set and a `rank` array to optimize the `union` operations (union by rank). We then iterate through the `isConnected` matrix. For every direct connection found between two cities `i` and `j`, we call the `union` operation on them.

The `union(i, j)` operation finds the representatives of the sets for `i` and `j`. If they are different, it merges the two sets and decrements the total province count. To make the `find` operation faster, we use path compression, which flattens the structure of the trees representing the sets.

After checking all pairs of cities, the final value of our province counter is the answer.

```java
class Solution {
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        UnionFind uf = new UnionFind(n);
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (isConnected[i][j] == 1) {
                    uf.union(i, j);
                }
            }
        }
        return uf.getCount();
    }
}

class UnionFind {
    private int[] parent;
    private int[] rank;
    private int count;

    public UnionFind(int n) {
        count = n;
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 0;
        }
    }

    public int find(int i) {
        if (parent[i] != i) {
            parent[i] = find(parent[i]); // Path compression
        }
        return parent[i];
    }

    public void union(int i, int j) {
        int rootI = find(i);
        int rootJ = find(j);
        if (rootI != rootJ) {
            // Union by rank
            if (rank[rootI] > rank[rootJ]) {
                parent[rootJ] = rootI;
            } else if (rank[rootI] < rank[rootJ]) {
                parent[rootI] = rootJ;
            } else {
                parent[rootJ] = rootI;
                rank[rootI]++;
            }
            count--;
        }
    }

    public int getCount() {
        return count;
    }
}
```
### Algorithm
- Create a Union-Find (or Disjoint Set Union) data structure initialized with `n` sets, one for each city. The number of provinces is initially `n`.
- The data structure should support `find` (with path compression) and `union` (with union by rank/size) operations.
- Iterate through the adjacency matrix `isConnected`. Since the matrix is symmetric, we only need to traverse the upper or lower triangle to avoid redundant checks.
- For each pair of cities `(i, j)` where `i < j` and `isConnected[i][j] == 1`, perform a `union(i, j)` operation.
- The `union(i, j)` operation will merge the sets containing `i` and `j` if they are not already in the same set. If a merge occurs, decrement the province count.
- After iterating through all connections, the remaining count of disjoint sets is the total number of provinces.

## Graph Traversal using Breadth-First Search (BFS)
This approach models the problem as finding the number of connected components in a graph. We can traverse the graph using Breadth-First Search (BFS). We iterate through each city. If a city hasn't been visited, it marks the beginning of a new province. We then start a BFS from this city to find and mark all cities belonging to the same province. The total number of times we initiate a BFS on an unvisited node gives us the number of provinces.
**Time:** O(n^2) - Each city is enqueued and dequeued exactly once. For each city, we iterate through its row in the adjacency matrix, which takes O(n) time. Thus, the total time complexity is O(n^2). · **Space:** O(n) - The `visited` array requires O(n) space. The queue can hold up to O(n) cities in the worst case.
**Pros:** It's an iterative approach, which avoids the risk of stack overflow that can occur with deep recursion in DFS.; Conceptually simple and a fundamental graph traversal algorithm.
**Cons:** BFS might have slightly more overhead due to queue management compared to a recursive DFS, though this is often negligible.
### Explanation
We use a boolean array `visited` to keep track of cities that have already been assigned to a province. We loop through all the cities from 0 to `n-1`. If we encounter an unvisited city `i`, we know it's part of a new province, so we increment our province counter. 

Then, we use BFS to find all cities connected to `i`. BFS is an iterative approach that uses a queue. We add city `i` to the queue and mark it as visited. Then, as long as the queue is not empty, we dequeue a city, check all its direct connections, and for any unvisited connected city, we mark it as visited and add it to the queue. This process ensures that all cities reachable from `i` are visited.

By the time the queue is empty, we have explored the entire province. We then continue our main loop to find the next unvisited city, which would belong to another province.

```java
import java.util.Queue;
import java.util.LinkedList;

class Solution {
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        boolean[] visited = new boolean[n];
        int provinces = 0;
        Queue<Integer> queue = new LinkedList<>();

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                provinces++;
                queue.add(i);
                visited[i] = true;
                while (!queue.isEmpty()) {
                    int u = queue.poll();
                    for (int v = 0; v < n; v++) {
                        if (isConnected[u][v] == 1 && !visited[v]) {
                            visited[v] = true;
                            queue.add(v);
                        }
                    }
                }
            }
        }
        return provinces;
    }
}
```
### Algorithm
- Initialize a `visited` boolean array of size `n` to keep track of visited cities.
- Initialize a `provinces` counter to 0.
- Iterate through each city `i` from `0` to `n-1`.
- If city `i` has not been visited:
  - Increment `provinces` count.
  - Start a Breadth-First Search (BFS) from city `i` to find all connected cities.
- The BFS traversal from a starting city `s`:
  - Create a queue and add `s` to it.
  - Mark `s` as visited.
  - While the queue is not empty:
    - Dequeue a city `u`.
    - For each city `v`, check if `u` and `v` are connected and if `v` has not been visited.
    - If so, mark `v` as visited and enqueue it.
- After the loop finishes, return the `provinces` count.

## Graph Traversal using Depth-First Search (DFS)
The problem of finding provinces is equivalent to finding the number of connected components in a graph. The cities can be seen as vertices and the connections as edges. A straightforward way to solve this is by using a graph traversal algorithm like Depth-First Search (DFS). We iterate through each city, and if it hasn't been visited yet, we start a DFS from it to find all connected cities, marking them as visited. Each time we start a new DFS on an unvisited node, we've found a new province.
**Time:** O(n^2) - We visit every cell of the `n x n` adjacency matrix at most once. The `dfs` function is called for each city. Inside `dfs`, we loop `n` times. Since we only enter the recursive call for unvisited cities, each city is processed once, leading to a total complexity proportional to the size of the matrix. · **Space:** O(n) - The `visited` array requires O(n) space. The recursion call stack can go up to `n` deep in the worst-case scenario (a path-like graph).
**Pros:** Intuitive and easy to implement using recursion.; The code is often more compact than an iterative BFS.; It is a very efficient and standard way to find connected components.
**Cons:** For very deep graphs, the recursion could lead to a stack overflow error. However, with the given constraint of `n <= 200`, this is not a concern.
### Explanation
The core of this approach is a `visited` array and a counter for provinces. We iterate through all cities from `0` to `n-1`. If we find a city `i` that has not been visited, we've discovered a new province. We increment our province counter and then start a DFS from city `i`.

The DFS is a recursive function that explores a graph as far as possible along each branch before backtracking. When we call `dfs(u)`, we first mark city `u` as visited. Then, we look at its row in the `isConnected` matrix. For every city `v` that is connected to `u` and has not been visited, we make a recursive call `dfs(v)`. This process continues until all cities in the same connected component (province) as `i` have been visited.

After the DFS for one component is complete, the main loop continues, searching for the next unvisited city, which will be the starting point of the next province.

```java
class Solution {
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        boolean[] visited = new boolean[n];
        int provinces = 0;
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                provinces++;
                dfs(i, isConnected, visited);
            }
        }
        return provinces;
    }

    private void dfs(int u, int[][] isConnected, boolean[] visited) {
        visited[u] = true;
        for (int v = 0; v < isConnected.length; v++) {
            if (isConnected[u][v] == 1 && !visited[v]) {
                dfs(v, isConnected, visited);
            }
        }
    }
}
```
### Algorithm
- Initialize a `visited` boolean array of size `n` to all `false`.
- Initialize a `provinces` counter to 0.
- Iterate through each city `i` from `0` to `n-1`.
- If `visited[i]` is `false`:
  - Increment `provinces`.
  - Call a recursive DFS function `dfs(i)` to explore its entire connected component.
- The `dfs(u)` function:
  - Mark the current city `u` as visited.
  - Iterate through all other cities `v`.
  - If `u` and `v` are connected (`isConnected[u][v] == 1`) and `v` has not been visited, make a recursive call `dfs(v)`.
- Return the final `provinces` count.

# Solutions
### Java

```java
class Solution { private int [][] g ; private boolean [] vis ; public int findCircleNum ( int [][] isConnected ) { g = isConnected ; int n = g . length ; vis = new boolean [ n ]; int ans = 0 ; for ( int i = 0 ; i < n ; ++ i ) { if (! vis [ i ]) { dfs ( i ); ++ ans ; } } return ans ; } private void dfs ( int i ) { vis [ i ] = true ; for ( int j = 0 ; j < g . length ; ++ j ) { if (! vis [ j ] && g [ i ][ j ] == 1 ) { dfs ( j ); } } } }
```

### CPP

```cpp
class Solution { public: int findCircleNum ( vector < vector < int >>& isConnected ) { int n = isConnected . size (); int ans = 0 ; bool vis [ n ]; memset ( vis , false , sizeof ( vis )); function < void ( int ) > dfs = [ & ]( int i ) { vis [ i ] = true ; for ( int j = 0 ; j < n ; ++ j ) { if ( ! vis [ j ] && isConnected [ i ][ j ]) { dfs ( j ); } } }; for ( int i = 0 ; i < n ; ++ i ) { if ( ! vis [ i ]) { dfs ( i ); ++ ans ; } } return ans ; } };
```

### Python

```python
class Solution : def findCircleNum ( self , isConnected : List [ List [ int ]]) -> int : def dfs ( i : int ): vis [ i ] = True for j , x in enumerate ( isConnected [ i ]): if not vis [ j ] and x : dfs ( j ) n = len ( isConnected ) vis = [ False ] * n ans = 0 for i in range ( n ): if not vis [ i ]: dfs ( i ) ans += 1 return ans
```