## Algorithm

Problem Name: 547. 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:

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

Example 2:

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

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
int findCircleNum(vector<vector<int>>& M) {
vector<int>Tags(M.size());
int tag = 0;
for(int i = 0; i  <  M.size(); i++){
if(Tags[i]) continue;
Tags[i] = ++tag;
for(int j = 0; j < M[0].size(); j++){
if(j == i || M[i][j] == 0) continue;
if(M[i][j]){
M[i][j] = M[j][i] = 0;
DFS(Tags, M, j, tag);
}
}
}
return tag;
}

void DFS(vector<int>& Tags, vector < vector<int>>& M, int row, int tag){
Tags[row] = tag;
for(int i = 0; i  <  M[row].size(); i++){
if(M[row][i]){
M[row][i] = M[i][row] = 0;
DFS(Tags, M, i, tag>;
}
}
}
};
``````
Copy The Code &

Input

cmd
isConnected = [[1,1,0],[1,1,0],[0,0,1]]

Output

cmd
2

### #2 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public int findCircleNum(int[][] isConnected) {
int n = isConnected.length;
Map < Integer, Set();
for (int i = 0; i  <  n; i++) {
for (int j = 0; j  <  n; j++) {
if (i != j && isConnected[i][j] == 1) {
map.computeIfAbsent(j, k -> new HashSet < >()).add(i);
}
}
}
Set visited = new HashSet<>();
int provinceCount = 0;
for (int i = 0; i  <  n; i++) {
if (!visited.contains(i)) {
while (!queue.isEmpty()) {
int removed = queue.remove();
for (Integer connection : map.getOrDefault(removed, new HashSet < >())) {
if (!visited.contains(connection)) {
}
}
}
provinceCount++;
}
}
return provinceCount;
}
}
``````
Copy The Code &

Input

cmd
isConnected = [[1,1,0],[1,1,0],[0,0,1]]

Output

cmd
2

### #3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const findCircleNum = function(M) {
let count = 0
const visited = {}
const dfs = function(M, i) {
for (let j = 0; j  <  M[i].length; j++) {
if (M[i][j] == 1 && !visited[j]) {
visited[j] = true
dfs(M, j)
}
}
}
for (let i = 0; i  <  M.length; i++) {
if (!visited[i]) {
dfs(M, i)
count++
}
}
return count
}
``````
Copy The Code &

Input

cmd
isConnected = [[1,0,0],[0,1,0],[0,0,1]]

Output

cmd
3

### #4 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def findCircleNum(self, m):
res, n = 0, len(m)
def explore(i):
m[i][i] = 0
for j in range(n):
if i != j and m[i][j] == m[j][j] == 1: explore(j)
for i in range(n):
if m[i][i] == 1: explore(i); res += 1
return res
``````
Copy The Code &

Input

cmd
isConnected = [[1,0,0],[0,1,0],[0,0,1]]

Output

cmd
3

### #5 Code Example with C# Programming

```Code - C# Programming```

``````
namespace LeetCode
{
public class _0547_FriendCircles
{
public int FindCircleNum(int[][] M)
{
var N = M.Length;
var uf = new UnionFind(N);
for (int i = 0; i  <  N; i++)
for (int j = 0; j  <  i; j++)
if (M[i][j] == 1)
uf.Union(i, j);

return uf.Count;
}

public class UnionFind
{
private int[] parents;

public UnionFind(int N)
{
parents = new int[N];
for (int i = 0; i  <  N; i++)
parents[i] = i;
Count = N;
}

public int Count { get; set; }

public int Find(int i)
{
if (parents[i] != i)
parents[i] = Find(parents[i]);

return parents[i];
}

public void Union(int i, int j)
{
var index1 = Find(i);
var index2 = Find(j);

if (index1 == index2) return;

parents[index1] = index2;
Count--;
}
}
}
}
``````
Copy The Code &

Input

cmd
isConnected = [[1,1,0],[1,1,0],[0,0,1]]

Output

cmd
2