OJ Board

I got WA. my algorithm is:
. first i tried to bicolor given graph.
. then put the same colored vertex in one class and others in another class.
. check that the two class satisfies the given constraints and print the result.

what is wrong with my algo? or give me the correct algo. Please help me.

What do you do if the graph is not bicolorable?

Yes i missed that case. But i am new at matching problems this is my first time. Can u help me?

This is not a matching problem.

Hint: take a random division into two groups. What is the probability that a fixed pair is split by this division? What is the expected value on the total number of pairs split?

Thanks a lot Per. I think ur are a great helper.

2 Per:
I am a little bit confused by your last post.

You want to say that we need to calculate probability
of splitting n/2 pairs and after that just do appropriate
number of random divisions. If feasible division was not found
then it is impossible to split graph in such a way.

Or you mean something else???

Actually, it is always possible, so I guess the "Impossible" was just there to fool people.

Yay Per! You found the solution that I was hoping someone would find. There is also a very simple greedy solution, but the randomized one is a lot more beautiful.

kp wrote:2 Per:
I am a little bit confused by your last post.

You want to say that we need to calculate probability
of splitting n/2 pairs and after that just do appropriate
number of random divisions. If feasible division was not found
then it is impossible to split graph in such a way.

No. I wanted to say exactly what I said.

Abednego wrote:Yay Per! You found the solution that I was hoping someone would find. There is also a very simple greedy solution, but the randomized one is a lot more beautiful.

Thanks, but I can't really claim to have found it... you'll hardly find any max-cut paper not mentioning it.
The greedy solution is essentially the derandomization of the randomized one, or are you talking about something else?

Maybe the greedy solution is the following: take vertices one by one, and put each of them in the class where it creates less number of pairs with already added vertices.

Yes, plus it is easy to see why:

Every "troublesome" pair will be considered exactly once (namely, when you have placed one of the members and are deciding where to put the other). At every decision, you "enable" at most half of the pairs that you are considering. Therefore, at the end, you will have "enabled" at most half the total number of pairs. QED.

what's the output for this input ?
1
5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

thx in advanced

For example,

There are a few output in this problem, aren't there ?



In Sample input .

4 3
1 2
2 3
3 4

->

output can be

1 3 4 / or / 2 / or / 2 3 ???




Then May I print one of them?








============================
sorry for my foor english

output can be
1 3 4 / or / 2 / or / 2 3 ???
Then May I print one of them?

Yes, you can print any of them. This is special judge problem.