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

# Check Bipartite Graph

Moderate
0/80
Average time to solve is 50m
Contributed by

## Problem statement

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â€™.

Note:
``````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 ( Input/output format, Notes, Images )
Constraints:
``````1 <= â€˜Tâ€™ <= 10
2 <= â€˜Nâ€™ <= 300
0 <= â€˜edges[i][j]â€™ <= 1.

Time Limit: 1sec.
``````

#### Sample Input 1 :

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

#### Sample Output 1 :

``````1
0
``````

#### Explanation of the Sample Input 1:

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

#### Sample Input 2 :

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

#### Sample Output 2 :

``````1
1
``````
Console