OJ Board

Getting WA. Could you give some 'tricky' tests ?

Input Output

Input Output

Nazmul Quader Zinnuree wrote:Input

Code: Select all

5
1 0
2 0
3 2
1 2
2 3
3 3
1 2
2 3
1 3
13 10
0 5
5 4
5 3
5 2
5 1
5 6
7 8
7 9
7 10
7 11

Output

Code: Select all

1
2
1
-1
3

I guess there is some error as examples 3 and 4 contain vertex number out of range. All other tests pass.

mamun wrote:Input

Code: Select all

3
5 2
0 1
2 3
5 3
0 1
2 3
1 3
4 3
2 0
2 1
2 3

Output

Code: Select all

3
3
1

Getting same results. Could some1 give an example of a solution that gets ACCEPTED.

what should be the approach for it...

when to return -1...
Cycle of odd length ???

vinay wrote:what should be the approach for it...

when to return -1...
Cycle of odd length ???

Yes, if the graph contains a cycle of odd length as a subgraph, you should write -1.

And for the other cases ?

DFS???

vinay wrote:And for the other cases ?

DFS???

Think about it. If you have a conected graph with no odd cycles as subgraphs, what are the only possibilities you can place guards, so they guard everything and do not interfere.

n/2 ??

vinay wrote:n/2 ??

Actually not, consider the graph K1,7 (complete bipartite graph with one vertex in the first partition and seven vertices in the second partition). It has 8 vertices, and just one gruard is enough.

I programmed maximum matching and was sure it is correct, but can not get my solution AC. Wish i new what is my problem and why there were so many resubmitions during the contest.

Problem can be solved without maximum matching.
Just think about bipartite graph and it's connected
components.

Edit: example of useless of maximum matching:

1
8 7
0 5
1 5
2 5
3 5
1 4
1 6
1 7

answer should be 4, but MM=2

forest wrote:I programmed maximum matching and was sure it is correct, but can not get my solution AC. Wish i new what is my problem and why there were so many resubmitions during the contest.

Consider the following graph: 0-1, 2-1, 1-3, 3-4 and 3-5. It's maximum matching is 2, but you need 3 guards.

think about bipartite graphs.
The tricky case is: The output should be 1 instead of 0.