The article from the series dedicated to problems of Mathematical Olympiad - category P (programming) shows two older competition tasks from 1993 and 1997 with different assignments, but almost identical solutions. While one task deals with the road network, the other deals with the relations of the guests at the party.

In both tasks, however, we actually determine whether the complement of the given undirected graph is bipartite. The second of the tasks differs only slightly in that we also determine the number of options for dividing the vertices of the graph into two groups.

The article explains the algorithm, shows its time complexity and also one possible way of implementation.