10505 - Montesco vs Capuleto

[lucindo]

windows2k,

In your DFS code seems that you aren't marking all nodes in the non-bipartite components. Try without recurtion.

[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...

[route]

Hi, everybody,

What is the output of the followings ?

1

5
1 2
1 3
1 4
1 5
0

[Observer]

Output should be 3.

[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)

[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?

[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.

[Larry]

I had it both ways and still WA.. any more inputs?

[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

[Larry]

Passed all those.. =( I really hate to post my code and just ask people, but maybe I'll have to..

[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

[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 (;

[Larry]

I took that into account, as it was one of the test cases above. Still any more sample codes?

[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

[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);
}