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

Problem of the day

Given a graph, check whether the graph is bipartite or not. Your function should return true if the given graph's vertices can be divided into two independent sets, â€˜Uâ€™ and â€˜Vâ€™ such that every edge (â€˜uâ€™, â€˜vâ€™) either connects a vertex from â€˜Uâ€™ to â€˜Vâ€™ or a vertex from â€˜Vâ€™ to â€˜Uâ€™.

You are given a 2D array â€˜edgesâ€™ which contains 0 and 1, where â€˜edges[i][j]â€™ = 1 denotes a bi-directional edge from â€˜iâ€™ to â€˜jâ€™.

```
If edges[i][j] = 1, that implies there is a bi-directional edge between â€˜iâ€™ and â€˜jâ€™, that means there exists both edges from â€˜iâ€™ to â€˜jâ€™ and to â€˜jâ€™ to â€˜iâ€™.
```

For example

```
Given:
â€˜Nâ€™ = 3
â€˜edgesâ€™ = [[0, 1, 1], [0, 0, 1], [0,0,0]].
```

Detailed explanation

```
The first line of input contains an integer â€˜Tâ€™ denoting the number of test cases.
The first line of each test case contains two space-separated integers, â€˜N,â€™ where â€˜Nâ€™ is the number of rows in â€˜edgesâ€™ and the number of columns in â€˜edgesâ€™.
The next â€˜Nâ€™ line of each test case contains â€˜Nâ€™ space-separated integers which tell if there is an edge between â€˜iâ€™ and â€˜jâ€™.
```

```
For each test case, You are supposed to return a bool value determining whether the graph is bipartite or not.
```

```
You are not required to print the expected output; it has already been taken care of. Just implement the function.
```

```
1 <= â€˜Tâ€™ <= 10
2 <= â€˜Nâ€™ <= 300
0 <= â€˜edges[i][j]â€™ <= 1.
Time Limit: 1sec.
```

```
2
4
0 1 0 0
0 0 0 1
0 0 0 0
0 0 0 0
3
0 1 1
0 0 1
0 0 0
```

```
1
0
```

```
In the first test case, the graph is visualized as below,
```

```
The graph can be divided into 2 disjointed sections, i.e. S1 = {0,2} and S2 = {1,3}. Therefore the answer is true.
In the second test case, the graph is visualized as below:
```

```
The answer is 0 since there is no way this graph can be divided into 2 disjoint sets of points.
```

```
2
4
0 0 1 0
0 0 0 1
0 0 0 0
0 0 0 0
3
0 1 1
0 0 0
0 0 0
```

```
1
1
```