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.