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 :)