New update is available. Click here to update.

Topics

You are given * ‘n’* cities, some of which are connected by bidirectional roads. You are also given an ‘n x n’ matrix i.e.

A province is a group of cities that are either directly or indirectly connected to each other through roads.

The goal is to count and return the total number of such provinces in the given matrix.

```
n = 4, roads = [ [1, 1, 1, 0],
[1, 1, 1, 0],
[1, 1, 1, 0],
[0, 0, 0, 1] ]
```

```
So, there are ‘2’ provinces.
```

```
1. A city is connected to itself. So, for every city ‘i’, ‘roads[i][i] = 1’.
```

Detailed explanation

```
3
1 0 0
0 1 0
0 0 1
```

```
3
```

```
Test Case 1:
n = 3, roads = [ [1, 0, 0],
[0, 1, 0],
[0, 0, 1] ]
```

```
So, there are ‘3’ provinces.
```

```
4
1 1 0 0
1 1 0 0
0 0 1 1
0 0 1 1
```

```
2
```

```
n = 4, roads = [ [1, 1, 0, 0],
[1, 1, 0, 0],
[0, 0, 1, 1],
[0, 0, 1, 1] ]
```

```
So, there are ‘2’ provinces.
```

```
1 <= 'n' <= 200
roads[i][j] is 1 or 0.
roads[i][j] == roads[j][i]
Time limit: 1 sec
```