Algorithm

The key point is that if a cycle has an even number of nodes, then there is no issue. But on the other hand, if it has an odd number of nodes, then the Bipartite condition fails. Because we only have 2 colors, if we have an odd number of nodes, definitely the starting and ending nodes will have the same color, but for even it won’t be.
Our color array basically has 3 states. It tells whether the node has been colored, if colored then whether it is the 1st color or 2nd one. In the checkBipartite function, we are initializing the color array with 1(not yet colored). We can use the color array to check whether a node is visited or not (we don’t need a separate visited array).
Then we are checking whether the node is colored or not. If it is not colored, we are coloring with the opposite color of its neighbor. That is, 1 color[node], gives 1 if the color[node] is 0 and 0 if the color[node] is 1. This is how we are inverting the color of the adjacencies.

Code

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566