> For the complete documentation index, see [llms.txt](https://docs-57.gitbook.io/data-structure-and-algorithms/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://docs-57.gitbook.io/data-structure-and-algorithms/problems/graph/number-of-provinces.md).

# Number of Provinces

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.leetcode.com/uploads/2020/12/24/graph1.jpg)

<pre><code><strong>Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]]
</strong><strong>Output: 2
</strong></code></pre>

**Example 2:**

![](https://assets.leetcode.com/uploads/2020/12/24/graph2.jpg)

<pre><code><strong>Input: isConnected = [[1,0,0],[0,1,0],[0,0,1]]
</strong><strong>Output: 3
</strong></code></pre>

&#x20;

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

```csharp
public class Solution {
    public int FindCircleNum(int[][] isConnected)
    {
        int num = 0;    
        bool[] visited=new bool[isConnected.Length];
        for (int i = 0; i < isConnected.Length; i++)
        {
            if (!visited[i])
            {
                FindCircleNum(isConnected, visited, i);
                num++;
            }
        }
        return num; 
    }
    public void FindCircleNum(int[][] isConnected, bool[] visited, int index)
    {
        if (visited[index])
        {
            return;
        }
        visited[index] = true;
        for (int j = 0; j < isConnected[index].Length; j++)
        {
            if (!visited[j] && isConnected[index][j] == 1)
            {
                FindCircleNum(isConnected, visited, j);
            }

        }
    }
}
```