Page 2 of 5
Posted: Mon Jul 14, 2003 4:34 pm
by lucindo
windows2k,
In your DFS code seems that you aren't marking all nodes in the non-bipartite components. Try without recurtion.
for windows2k
Posted: Tue Jul 15, 2003 3:50 pm
by zoho ho
try this
1
4
2 2 3
3 1 3 4
2 1 2
1 2
your answer is 1 , but the true answer is 0 ;
your DFS don,t mark node 4 and just return false ;
---------
huhuhu...
Re: for windows2k
Posted: Sat Jul 19, 2003 1:33 pm
by route
Hi, everybody,
What is the output of the followings ?
1
5
1 2
1 3
1 4
1 5
0
Posted: Sat Jul 19, 2003 3:25 pm
by Observer
Output should be 3.
DFS works just as fine
Posted: Tue Jul 29, 2003 3:41 am
by Nick
Hi, I use DFS on this problem and accepted just fine. I think its the coloring of the vertices that really matters, not the way you traverse the graph (for this kind of problems)
Posted: Sun Oct 05, 2003 9:09 am
by Larry
Anyone have any more test cases? I past all on this board, and still WA.
I basically use the algorithm everyone else described..
10
3
1 1
1 2
1 3
10
1 2
1 3
0
0
0
0
0
0
0
0
8
2 2 4
1 3
1 4
0
3 6 7 8
2 7 8
1 8
0
4
2 2 3
3 1 3 4
2 1 2
1 2
5
1 2
1 3
1 4
1 5
0
0
1
1 613
5
1 3
1 1
0
1 5
0
8
2 4 5
2 1 3
0
0
0
1 3
0
1 5
3
2 2 3
1 3
1 1
is what I used and I get:
3
9
2
0
3
0
1
3
5
0
Am I incorrect anywhere?
Posted: Sun Oct 05, 2003 7:17 pm
by Per
The first test case should be 0, though I'm not sure there are any test cases like that in the input.
The rest of your output is correct.
Posted: Sun Oct 05, 2003 8:53 pm
by Larry
I had it both ways and still WA.. any more inputs?
Posted: Tue Oct 07, 2003 11:12 am
by hujialie
Hi,Larry.
Here are some tests where I found my mistake.
Hope it can help.
INPUT:
3
10
0
0
0
0
0
0
0
0
0
0
13
2 2 3
2 1 5
4 1 5 7 8
0
4 2 3 6 12
1 5
1 3
2 3 11
1 10
1 9
1 8
1 5
0
13
1 2
2 3 6
2 4 7
1 9
3 6 8 12
1 13
0
2 9 11
0
2 11 12
0
1 13
0
OUTPUT:
10
8
0
Posted: Tue Oct 07, 2003 8:31 pm
by Larry
Passed all those.. =( I really hate to post my code and just ask people, but maybe I'll have to..
10505 Montesco vs Capuleto
Posted: Mon Oct 27, 2003 2:39 am
by fpmc
Hi, I'm kind of struggling with this problem.
It says that the 'enemy' relationship is anti-symmetric
ie. aRb and bRc -> not aRc
but in the sample input, we have
3
2 2 3
1 3
1 1
which is not anti-symmetric.
Can anyone give me some pointers in handling the case where it's not anti-symmetric? Do I ignore the anti-symmetric rule altogether?
Frank
Posted: Fri Dec 19, 2003 1:00 am
by GigS
There exsists test where number of enemy is bigger than N
for example
1
1 2
add a line
[i]if(a>n)continue; [/i]
in reading function should work (;
Posted: Thu Jan 15, 2004 2:02 am
by Larry
I took that into account, as it was one of the test cases above. Still any more sample codes?
Posted: Wed Mar 24, 2004 12:09 am
by Fzaila
Can anybody tell me how i can get the input given by the Judge?
Becoz i am getting the WRONG ANSWER, although all of the sample inputs given in this forum + other inputs giving me the right answer. but judge is giving WRONG ANSWER .
Will somebody help me?
Thanks
Posted: Tue Jul 04, 2006 9:44 pm
by Khaled_912
You must consider the graph as 'components', and count components that are not bipartite as 0.
Here is my DFS code:
Code: Select all
void dfs(int x, int c)
{
if (v[x]) //visited
{
if (col[x] != c) bipartite = false; //color mismatch
return;
}
v[x] = true;
col[x] = c; //set the color
//add the code for counting the node here
int nc = inv(c); //the inverse of the color.. 0->1 and 1->0
for (int i = 0 ; i < n ; i++)
if (a[x][i]) dfs(i, nc);
}