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