Bipartiteness check

Bipartiteness check

Bipartiteness Check

Statement

You are given an undirected graph. Check whether it is bipartite, and if so, output its parts.

Solution

There is a theorem: a graph is bipartite if and only if all its cycles have even length.
However, in practice it is more convenient to use another formulation: a graph is bipartite if and only if it is two-colorable.

We use DFS (you can also, as in the previous problem, use BFS), starting from each vertex that has not yet been visited. In each search, we assign the vertex from which we start to side 1 (for example, color 0). Each time we visit an unvisited neighbor of a vertex from one side, we assign it to the other side.

If we try to move to a neighbor that has already been visited, we check that it is on the other side. If it turns out to be on the same side, we conclude that the graph is not bipartite.

After we have visited all vertices and successfully distributed them into sides, we know that the graph is bipartite, and we have constructed its partition.