10505  Montesco vs Capuleto
Moderator: Board moderators
for windows2k
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...
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...
I have not ICQ or any online Messenger
If you want tell me any private you can
send mail to
u89156@ice.ntnu.edu.tw
thank you !
If you want tell me any private you can
send mail to
u89156@ice.ntnu.edu.tw
thank you !
Re: for windows2k
Hi, everybody,
What is the output of the followings ?
1
5
1 2
1 3
1 4
1 5
0
What is the output of the followings ?
1
5
1 2
1 3
1 4
1 5
0
Output should be 3.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
DFS works just as fine
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)

 Guru
 Posts: 647
 Joined: Wed Jun 26, 2002 10:12 pm
 Location: Hong Kong and New York City
 Contact:
Anyone have any more test cases? I past all on this board, and still WA.
I basically use the algorithm everyone else described..
I basically use the algorithm everyone else described..
is what I used and I get: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
Am I incorrect anywhere?3
9
2
0
3
0
1
3
5
0
10505 Montesco vs Capuleto
Hi, I'm kind of struggling with this problem.
It says that the 'enemy' relationship is antisymmetric
ie. aRb and bRc > not aRc
but in the sample input, we have
3
2 2 3
1 3
1 1
which is not antisymmetric.
Can anyone give me some pointers in handling the case where it's not antisymmetric? Do I ignore the antisymmetric rule altogether?
Frank
It says that the 'enemy' relationship is antisymmetric
ie. aRb and bRc > not aRc
but in the sample input, we have
3
2 2 3
1 3
1 1
which is not antisymmetric.
Can anyone give me some pointers in handling the case where it's not antisymmetric? Do I ignore the antisymmetric rule altogether?
Frank

 New poster
 Posts: 33
 Joined: Fri Jan 06, 2006 5:51 pm
You must consider the graph as 'components', and count components that are not bipartite as 0.
Here is my DFS code:
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);
}