Given an adjacency list of a graph with "v" vertices (0 to v-1), check whether the graph is bipartite or not.
In a Bipartite graph, one can color all the nodes with exactly 2 colors such that no two adjacent nodes have the same color.
Solutions
Method 1: Using DFS
If the graph is disconnected, then call the function for individual trees (start from each non-colored node).
As the problem statement says, in a bipartite graph, all the nodes can be painted with exactly 2 colors, such that no two adjacent nodes have the same color.
Start traversing the graph in a DFS manner and keep track of the node's colours in the color[] array. (0-not visited, 1-color1, 2-color2)
Also keep track of the parent node's colour, and if the current node has not yet been visited, give it the colour opposite to its parent.
On the other hand, if the current node is already visited and its colour is the same as its parent, that means two adjacent nodes have the same colour and the graph is not bipartite.
Complexity
The time complexity of this solution is O(v+e) and space complexity is O(v).