Cateva idei despre rezolvare. In primul rand, problema este NP-copmleta, 
deci rezolvarea trebuia sa fie, intr-un fel sau altul, o cautare 
exhaustiva inspatiul solutiilor. Cea mai simpla idee era incercarea pe 
rand a fiecarei combinatii posibile deverigi. Aceasta varianta se incadra 
rezonabil in timp (eventual cu micioptimizari) intrucat 2^20 ~= 1000000.

Pentru fiecare combinatie de verigi dechise trebuie sa verificam daca 
ele formeaza o solutie. Procedeul este:

1) Se considera subgraful obtinut prin eliminarea respectivelor verigi 
(si bineinteles a muchiilor adiacente in graf, pentru ca o veriga 
desfacuta nu ma ieste legata de nici o alta veriga)
2) Acest graf trebuie sa fie format numai din lanturi
3) Fie V numarul de verigi deschise si L numarul de lanturi obtinute in 
   subgraf. Atunci trebuie sa avem V>=L+1, ca sa putem folosi verigile 
   pentru a interconecta lanturile .Cum verificam rapid daca un graf e 
   format numai din lanturi, si cum aflam acest numar de lanturi? 
   Raspunsul se poate da in O(n):
     a) Toate nodurile trebuie sa aiba gradul cel mult 2. Aceasta 
        conditie este "aproape suficienta", mai trebuie sa ne asiguram 
        ca graful nu contine cicluri.
     b) Efectuam o parcurgere a grafului pentru a detecta eventualele 
        cicluri
     c) Fie n numarul de noduri din graf, si fie d suma gradelor tuturor
        nodurilor.Atunci se arata usor ca numarul de lanturi este n-d/2, 
        intrucat d/2 este tocmainumarul de muchii din graf. 

Nu am implementat personal o sursa, dar sursa lui Mugurel se incadreaza
perfect in timp. Nu am fost chiar sigur daca timpul de o secunda e suficient
pana nu am vazut o sursa care sa mearga :)