Description

Continuing with the theme of augmenting data structures, this problem requires you to construct a graph and determine if it can be bicolored. That is you must determine whether or not the vertices of the graph can be painted red and black such that no two adjacent nodes have the same color [1].

For example, consider the graph to the right, which is an example of a bicolorable graph. Graphs that contain this ability to bicolored are also called bipartite graphs.

In this problem, you can assume the graph is connected, undirected, and does not have self-loops. Your solution should be O(N) and ideally contain only one traversal of the graph.

Input

The input will be a series of graphs. Each graph specification will begin with the number of vertices, followed by the number of edges, and the pairs of vertices denoting the edges. The end of the input will be marked by a 0 as the number of vertices. Sample input:

3
3
0 1
1 2
2 0
9
8
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0

Output

For each graph output whether or not it is bicolorable as shown in the sample output:

NOT BICOLORABLE
BICOLORABLE

[1]	Hmm. I think DChen also assigned this problem to my Algorithms class, way back in the day...

Approach

Simply start coloring the graph, knowing that all the neighbors of the current node must be the opposite color. If this rule is violated, then we know that the graph is not bicolorable.

Input/Output

• Final Input: problem012.input
• Final Output: problem012.output

Source Code

• Peter Bui's source code: pbui.cc
• Noah Franske's source code: nfranske.cc
• Jared Zenk's source code: jzenk.cpp