1. JAVA, Gunnar Hage


/**
* FWP-Fach: ACM programming Contest WS 08/09 "10004 - Bicoloring"
* Verdict: not commited
*
* Gunnar Hage, gunnarhage@gmx.de
* AP5(IFB5A) Jan. 2009
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

//2 Testfälle
Output:

NOT BICOLORABLE.
BICOLORABLE.

*/
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main {

static boolean[][] adja;

public static void main(String... args) throws IOException{
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int nodes;
int edges;
int start, end;
StringTokenizer st;
nodes = Integer.parseInt(br.readLine());
while(nodes != 0){

adja = new boolean[nodes][nodes];
edges = Integer.parseInt(br.readLine());
for(int i=0;i<edges;i++)
{
st = new StringTokenizer(br.readLine());
start = Integer.parseInt(st.nextToken());
end = Integer.parseInt(st.nextToken());
adja[start][end] = true;
adja[end][start] = true;
}
if(fill())
bw.append("BICOLORABLE.\n");
else
bw.append("NOT BICOLORABLE.\n");
nodes = Integer.parseInt(br.readLine());
}
bw.flush();
bw.close();
System.exit(0);
}

private static boolean fill() {
boolean[] color = new boolean[adja.length];
boolean[] visited = new boolean[adja.length];
boolean[] origin = new boolean[adja.length];
int node = 0;
visited[0] = true;
int originCount = 0;


//Solange nicht alle Knoten als Ursprung gedient haben.
while(originCount < adja.length)
{//findet den ersten Knoter der noch nicht origin war. Aber schon einmal besucht wurde.
for(int i=0;i<adja.length;i++)
if(!origin[i] && visited[i])
{
node = i;
origin[i] = true;
originCount++;
i = 201;
}
//Für alle Knoten
for(int i=0;i<adja.length;i++)
{
if(adja[node][i]) // zu denen eine Verbindung besteht,
{
if(visited[i]) // schau nach ob der Knoten schon einmal besucht wurde.
{// Wenn ja und die beiden Knoten die gleiche Farbe haben.
if(color[i] == color[node])
return false; // ist der Graph nicht Bipartit.
}
else
{//Wenn er noch nicht besucht wurde,
visited[i] = true; // als besucht markieren.
color[i] = !color[node]; // Die komplementärfarbe des aktuellen knoten setzen.
}
}
}
}
//Wenn alle Knoten besucht wurden und keine Unstimmigkeit gefunden wurde,
return true;
}
}