Hello guys. I'm trying to solve the problem Circuits from spoj. After think a lot, I found a greedy solution to solve this problem, follow
'Supposing all components have no cycles yet'
1) Separate all components
2) Get the component with less vertices and the component with most vertices.
3) Merge this two componentes this way:
A = first component
B = second component
From A, get the two vertices (may be the same vertex) that have the greater distante.
From B, the same thing.
4) Create a link (connect the vertices from A and B) between this four vertices:
graph[A[0]].push_back(B[0]);
graph[B[0]].push_back(A[0]);
graph[A[1]].push_back(B[1]);
graph[B[1]].push_back(A[1]);
5) Find the formed cycle (and all vertices on the cycle)
6) For each node in the cycle:
If the node have all the neighbors in the cycle, I just remove it.
7) Generate again the componentes, and the process repeats until I find nodes without a cycle.
I guess this algorithm above work fine (at least I tested in several cases). But it is very complicated.
Does anyone agree with this solution or I can do something easier ? Sorry for the long text and my poor english.
40 hours passed and nobody got interested! I think, you should change the blog title to get the answer.
I think to the condition be fulfilled every vertex must be connected to at least 2 edges. This way, we only need to store the ones with less than 2 edges into a container and add edges to them (just increase their degree). Note that it's always good to add a edge between vertices in this condition (less than 2 edges). The final answer should be the number of added edges.
I haven't coded the problem, so my thinking may be wrong. Any suggestions/thoughts are welcome.
I guess this problem is not so simple, look at this test case:
The answer is 2(linking vertex 2-6 and 4-5). Using your strategy, what vertex should I choose to do that ?
Yeah, the strategy is definitely wrong.
I wrote this algorithm Solution, my solution fails in the first test case (the answer should be 1).
I Think your solution is wrong because I have a counter example in which every vertex has degree 2 or 3 but answer is not 0
n = 7
m = 8
edges :
1 , 2
2 , 3
1 , 3
3 , 4
4 , 5
5 , 6
6 , 7
7 , 5
UP : It was really interesting when I read the comments in problem page on spoj ! because some one said my example in comments there ! but I really didn't copy the example from there !
Yeah, the strategy is definitely wrong.
Oh yes, this solution is wrong. I found a test case that it never works. Also, me and a friend, we find the solution. Haha it is amazing.
Could you explain how the correct strategy works?
Yes, I just need to implement, but I'm almost sure that it works: The first thing is to see that the bridges is the key to solve. After get the bridges, you have to separate the componentes and compress them (if a edge is not a bridge, compress). After this, you have a tree. Now I guess you can get the answer.
I generated several test cases, a little later I send the expected answers for those tests.
I tried to solve this problem for a couple of hours and couldn't come up with anything. I thought max-flow, greedy, I even thought of that "degree of at least 2" solution, but none of them worked.
Moreover, this problem is from Argentinian National Tournament 2011, and no one solved it there either, so it looks like it's indeed pretty hard.
It is not too hard as you think. :) I've spent a lot of hours in this problem too..
Try something involving 'bridges'.. I hope it help. See my comment above.
The correct answers: http://pastebin.com/h1thArsT