Problem of the day
The graph has no self-edges, no parallel edges.
The graph may not be connected.
A graph is bipartite if the nodes of the graph can be partitioned into two independent sets A and B such that every edge in the graph connects a node in set A and a node in set B.
If βNβ = 4, βMβ = 5, edgeList = [ [0, 1],[0, 3],[1, 2] ].
Here, you can see that the graph is bipartite as we can divide the nodes in two sets as follows:
setA = [0, 2].
setB = [1, 3].
In the graph, you can see that every edge in the graph connects a node in set A and a node in set B.
Hence, the output is βYesβ.
The first line of input contains an integer βTβ denoting the number of test cases. then βTβ test cases follow.
The first line of each test case consists of two space-separated integers βNβ, βMβ, representing the number of nodes and the number of edges of the graph.
Then next βMβ lines follow in each test case. The ith line consists of two space-separated integers βEDGES[i][0]β and βEDGES[i][1]β representing that there is a undirected edge between nodes βEDGES[i][0]β and βEDGES[i][1]β.
For each test case, print the βYesβ if the given graph is bipartite, Otherwise, print βNoβ.
Print a separate line for each test case.
You do not need to print anything, it has already been taken care of. Just implement the given function.
1 <= T <= 10
1 <= N <= 500
1 <= M <= (N * (N - 1)) / 2
Time limit: 1 sec
2
4 3
0 1
0 3
1 2
4 5
0 1
0 3
1 2
2 3
0 2
Yes
No
For the first test case, the graph will be:
Here, you can see that the graph is bipartite as we can divide the nodes into two sets as follows:
setA = [0, 2].
setB = [1, 3].
In the graph, you can see that every edge in the graph connects a node in set A and a node in set B.
Hence, the output is βYesβ.
For the second test case, the graph will be:
Here, you cannot divide the nodes into two independent sets A and B such that every edge in the graph connects a node in set A and a node in set B. Hence, the output is βNoβ.
2
4 4
0 1
0 2
0 3
2 3
3 3
0 2
1 0
1 2
No
No