I think there are some things missing in your code.
First you just insert the edge from input[0] to input[1] and not the backedge. In the problemstatement its clearly said that we have nondirectional edges.
Another thing is that you go through the nodes by there number. You should do a DFS (or BFS) in this task, so you should work on the nodes when you find them, not in the ranking of there number. You can use a stack for solving this problem.
Last thing is that i am not sure with these lines:
I think, but i am not very familiar with C, that you write two times on the same position in the array, so your edge is deleted. Second thing is that you search for first -1 in the adj field, but when you found it you Increment j so you are behind the first -1 and the edge wont be find.
hello, every1, this is my first time posting, im having problem with this problem, i keep getting wa even tho i passed the sample test, can some1 help thx!
nvm i got it thx
Welcome to all new commers ....
BFS or DFS or simple recurrence anyone can do it just use the color=step%2;
Is :the preveous color is ok then return and carry on..
Else :not bicolorable
Good Luck...
when 10004 done,i meet a strange question: when i try several input/output myself ,it do the right thing,but in the online-judge,receive WA,but i don't know why.would anybody help me ?thank you very much!
my idea is DFS,every expanded node's color is opposite to the father's(implemented by using variable color_set).Here is my code:
hi, i really need help. i've checked my program against some test cases and they're rite. but when i submit, i get WA! i really dunno how to further debug cus i dun even know wats the mistake.
import java.io.*;
import java.util.*;
class Main {
// flag used to check for non-bicolorable.
// 1 = bicolorable. 0 = non-bicolorable
int bicolorFlag = 1;
// # of edges, # of vertices
int e = 0, v = 0;
// color code used in colorVertice[]
int black = 1, red = 2;
// this matrix shows link between vertices
int vertice[][];
// this array shows the color of each vertice
int colorVertice[];
StringTokenizer st;
public static void main(String args[]) {
Main ms = new Main();
ms.setUpGraph();
}
// set up graph based on number of edges and vertices
void setUpGraph() {
String temp;
if((temp = Main.readLn(255)) != null) {
v = Integer.parseInt(temp);
}
// check if vertice = 0
if(v == 0) {
//normal termination
System.exit(0);
}
else {
if((temp = Main.readLn(255)) != null) {
e = Integer.parseInt(temp);
}
}
vertice = new int[v][v];
colorVertice = new int[v];
// pair of vertices tt are linked
int v1, v2;
// picks one vertice to be e first node.
int firstNode = 0;
boolean firstNodePicked = false;
for(int i=0; i<e; i++) {
if((temp = Main.readLn(255)) != null) {
st = new StringTokenizer(temp);
v1 = Integer.parseInt(st.nextToken());
v2 = Integer.parseInt(st.nextToken());
if(firstNodePicked == false) {
firstNode = v1;
firstNodePicked = true;
}
// 1 to indicate there's an edge between these 2 vertices
vertice[v1][v2] = 1;
vertice[v2][v1] = 1;
}
}
// start color process of graph
colorGraph(firstNode);
if(bicolorFlag == 0) {
System.out.println("NOT BICOLORABLE.");
}
else if(bicolorFlag == 1) {
System.out.println("BICOLORABLE.");
}
setUpGraph();
}
// colors the first node(0) first
void colorGraph(int first) {
// if first node is not colored, color it red
if(colorVertice[first] == 0) {
colorVertice[first] = red;
}
colorChild(first);
}
// color the child of the curr parent node
void colorChild(int currParent) {
for(int currChild=0; currChild<v; currChild++){
// if not pointing to itself
// there's edge between currChild and currParent
// currChild has color like parent (indicates non-bicolorable)
if(vertice[currChild][currParent] != vertice[currParent][currParent]
&& vertice[currChild][currParent] == 1
&& colorVertice[currChild] == colorVertice[currParent]) {
// set the flag
bicolorFlag = 0;
// will break out of for loop
break;
}
// if not pointing to itself
// there's edge between currChild and currParent
// currChild has not been colored before
else if(vertice[currChild][currParent] != vertice[currParent][currParent]
&& vertice[currChild][currParent] == 1
&& colorVertice[currChild] == 0) {
//alternate the colors between parent and child
if(colorVertice[currParent] == red)
colorVertice[currChild] = black;
else
colorVertice[currChild] = red;
// set the flag
bicolorFlag = 1;
}
}
// only if suits bicolorable criteria
// and curr vertice still within given # of vertices
if(bicolorFlag == 1 && currParent+1 < v) {
colorChild(currParent+1);
}
}
static String readLn (int maxLg) {
byte lin[] = new byte [maxLg];
int lg = 0, car = -1;
String line = "";
try {
while (lg < maxLg) {
car = System.in.read();
if ((car < 0) || (car == '\n')) break;
lin [lg++] += car;
}
}
catch (IOException e) { return (null); }
if ((car < 0) && (lg == 0)) return (null);
return (new String (lin, 0, lg));
}
}
earlier I solved this problem using a different approach but this time i tried to use Floyd warshall algorithm to solve it..
Using FY , i tried to find cycles in it of length 3.
ie. if i is connected to j and if i is also connected to k and k is connected to j then its Not Bicolrable.
i checked my program by many input cases.......still i am getting wrong answer.
Please check my program and verify with input cases . And tell me for what input cases my program is wrong........
My program is given below..
