Bicoloring
From CS371p
The Bicoloring problem description UVA Online Judge
The Bicoloring problem is a graph searching problem.
The nodes in a Bicolor graph mush be sortable into two sets, such that no edge points to another node within its own set.
This is also know as a Bipartite Graph
The solution to this problem is to "color" each node as you visit each node. Take this example for instance,
- 3
- 3
- 0 1
- 1 2
- 2 0
The first line of "3" is the number of nodes. If the first line of the test case was a "0" you would end your program. The second line of "3" is the number of edges. The last three lines, indicate the edges. "0 1" indicate an edge from Node 0 to Node 1, and a edge from Node 1 to Node 0. "1 2" indicate an edge from Node 1 to Node 2, and a edge from Node 2 to Node 1. "2 0" indicate an edge from Node 2 to Node 0, and a edge from Node 0 to Node 2.
Algorithm
To solve this problem, you must keep track of each node you visit and the "coloring" of each node. Each node starts as unvisited. To color a Bicoloring graph, we only need 3 values,
- To indicate Set 1
- To indicate Set 2
- To indicate an unvisited Node.
We start with a node, and check if the node is visited. If the node is visited we move to the next node. If the node is unvisited, we color this node to indicate it belonging to a set. Now we check the edges from the node, we follow each edge from the node to other nodes. If we find a node with the same coloring we can stop and print "NOT BICOLORABLE." because we have a node within a set that is connected to another node within the same set.
If you travel the graph and color each node without finding an edge connected node with the same coloring, you have a "BICOLORABLE." graph.
You can use a depth first search the graph. Be sure to use "NOT BICOLORABLE." and "BICOLORABLE.", without the quotes and with the period. Also remember to reset your data structures used to keep track of node and edge data.
