OJ Board

Hi,

could someone give some test cases, i don't know what i'm doing wrong

thanks

Try this: Correct output is: (edited to make it correct)
Case #1: Impossible
Case #2: Impossible

hmm, possible i missunderstood something, but second test is something like this:
__3
|
1--2
|
5--4
|
6

so maximum independent set is {2,3,4,6} and minimum vertex cover is {1,5}, so answer is impossible?

Am i rigth? Or simple so stupid that i haven't understood this task?

-- Post removed by Observer --

Actually, it seems my program is wrong.
I agree the largest independant set for the second test case should be {2, 3, 4, 6}, and minimum vertex cover {1,5}.
I wonder why I got Accepted.

Hmm... probably the problemsetter has mistaken "maximum" as "maximal" then.. or maybe the test cases are just too simple ?

Edit: spoiler removed

exactly i do the same and i'm sure that this is correct algo


(***cut after acc***)

edit:
almost sure

This problem is wrong. I'll fix it today.

Actually, just so that I don't screw it up again, Adrian or Monsoon, could you send me your solution please? (abednego at gmail)

igor

pls anyone give some hits to solve this problem.

one hint: think what is when graph is bipartite and what is when it's not

Monsoon wrote:one hint: think what is when graph is bipartite and what is when it's not

thx for the hit. i already think that. But if the given graph is bipartite, then it's not sure that there is an answer. am i right ? Now tell me :

1. if the total node is odd, then its "Impossible".
2. if the graph is bipartite and the given graph has an answer, then the output will be left part of the bipartite graph(i.e which part contais 1st node).

Am i right ?

Now tell me abt the minimum vertex cover portion. what's the way to handle this part ? A graph has no answer if not bipartite or it's minimum vetex set size != total node / 2. right ?

hope u get my problem.
pls help.

You are right.
For minimum vertex cover, there exists an efficient algorithm if the graph is bipartite (which you can check first). Hint: Think about how you can find a lower bound for the minimum number of nodes in the vertex cover (it turns out, if you find the right lower bound, that it is in fact the solution).
I guess, that the algorithm is also mentioned in some books about graph theory.

Hmm. 1 Accepted and 34 Presentation Errors. Could it be that the judge has the wrong format? I'm (almost) sure my output is correctly formatted, but it's one of the 34.
No big deal, just want to mention it.

I had the same problem with presentation error, I don't know what's wrong, but definitely there's some problem with the judge's output format. I'm sure mine is correct.