Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Problem of the day

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