The BipartiteX class represents a data type for determining whether an undirected graph is bipartite or whether it has an odd-length cycle. The IsBipartite operation determines whether the graph is bipartite. If so, the Color operation determines a bipartition; if not, the OddCycle operation determines a cycle with an odd number of edges.

This implementation uses breadth-first search and is nonrecursive. The constructor takes time proportional to V + E (in the worst case), where V is the number of vertices and E is the number of edges. Afterwards, the IsBipartite and Color operations take constant time; the OddCycle operation takes time proportional to the length of the cycle. See for a recursive version that uses depth-first search.