I was trying to solve this problem http://lightoj.com/volume_showproblem.php?problem=1201 on LightOJ. My algo was to split the graph into two sets (vectors A and B) (since the graph is undirected and acyclic and so bipartite). Then I found the maxBPM from A to B and the answer is number of nodes-maxBPM.
Here is my cod: http://paste.ubuntu.com/8170061/
What is my mistake actually?
Problem Description:
"Yes, I am the murderer. No doubt" I had to confess it in front of all. But wait, why I am confessing? Nobody wants to go to jail, neither do I. As you have suspected there is something fishy. So, let me explain a bit.
The murder was happened in 19th June, at 11:30 pm this year (2009) according to the medical report. So, I was asking the judge "Can you find the time 19th June 11:30 pm in Bangladesh?" The judge informed other reporters to find the time. But alas! There was no time — "2009, 19th June, 11:30 pm". So, the judge got a bit confused about my confession. So, I began to tell them, "The time the murder was happened, is not a valid time according to you. So, how can you claim that I am the murderer?"
And what happened next, you all know. I am in the streets again with a clean sheet.
But now I have planned to kill again. I have a list of N mosquitoes which are to be killed. But there is a small problem. If I kill a mosquito, all of his friends will be informed, so they will be prepared for my attack, thus they will be impossible to kill. But there is a surprising fact. That is if I denote them as a node and their friendship relations as edges, the graph becomes acyclic.
Now I am planning when and how to kill them (how to get rid of the law!) and you have to write a program that will help me to find the maximum number of mosquito I can kill. Don't worry too much, if anything goes wrong I will not mention your name, trust me!
Input Input starts with an integer T (≤ 50), denoting the number of test cases.
Each case starts with a blank line and two integers N (1 ≤ N ≤ 1000) denoting the number of mosquito I want to kill and M denoting the number of friendship configurations. Each of the next M lines contains two integers a and b denoting that ath and bth mosquitoes are friends. You can assume that (1 ≤ a, b ≤ N, a ≠ b) and each friendship relation is given only once. As I have already mentioned, you will not find any cycle in the relations.
Output For each case, print the case number and the maximum number of mosquitoes I can kill considering the conditions described above.
Sample input output here: http://paste.ubuntu.com/8171545/
I will remind you that if you want to get any help here about a problem from LightOJ, please copy and paste the problem text here. Not all of the Codeforces users are registered there.
I have done the same. Thank you for your suggestion.
Would you please check it now?
I don't think your splitting of sets A and B works as you expect. Take this graph for instance:
If I'm right, your code will split sets as A B B A instead of A B A B. The key here is to realize that when you assign a vertex to a set, all neighbors are in the other set, which implies all neighbors of neighbors are in the original set, etc. You can implement this using DFS or BFS quite easily.
As an aside, you do know find () takes time proportional to the size of vector, right? Creating a separate vector to indicate to which set each vertex belongs would make it a constant time operation. And your ms () macro only works as intended if you want to set to -1 or 0, if you don't know that as well.
Thanks for your help and also for your advice ffao :)
Understood my mistake. Thanks again!