h2. Plimbare
Evident ca o conditie necesara ca un graf turneu (asa se numesc grafurile ca cel mentionat in enunt in care exista exact un arc intre oricare doua noduri) sa aiba un circuit hamiltonean ar fi ca graful sa fie tare conex, daca nu ar fi tare conex atunci evident nu poate exista un circuit intre doua noduri aflate in doua componente tari conexe diferite. Aceasta conditie este si suficienta asa cum va reiesi din algoritmul pe care il vom explica mai jos.

Astfel pentru graful nostru vom determina componentele tari conexe, si vom cauta un circuit hamiltonean in cea mai mare dintre acestea. De acum ne vom concentra doar asupra nodurilor acestei componente. Evident ca aceasta componenta conexa contine cel putin un circuit, pentru a determina unul facem o cautare in adancime, si trebuie sa gasim la un moment dat o muchie de intoarcere (pentru ca altfel componenta nu ar fi tare conexa). Vom imparti nodurile din aceasta componenta in patru multimi: $A$ multimea nodurilor din circuit, $B$ multimea nodurilor din afara circuitului pentru care exista si arce orientate de la noduri din circuit la ele, si arce orientate de la ele la noduri din circuit, $C$ multimea nodurilor din afara circuitului pentru care exista numai arce ce pornesc din circuit inspre noduri, si $D$ multimea nodurilor pentru care toate arcele intre ele si noduri din circuit sunt orientate de la ele inspre circuit. Puteti observa ca nodurile din multimea $B$ pot fi inserate tot timpul in circuit undeva inlocuind un arc intre doua noduri ale circuitului cu doua arce de la un nod al circuitului la nodul multimii $B$ si apoi la alt nod din circuit. Inserarea unui astfel de nod dureaza maxim $O(n)$ pasi, alti $O(n)$ pasi ar fi necesari pentru modificarea multimilor $B, C, D $ pentru ca circuitul s-a schimbat. Dupa ce nu ne mai ramane nici un nod in $B$. Ramanem doar cu noduri de tip $C$ sau $D$. Orice nod din multimea $C$ va avea cel putin un arc orientat spre alt nod din multimea $D$ pentru ca altfel nu am fi intr-o componenta tare conexa. Acum aceste doua noduri legate printr-o muchie dinspre $C$ inspre $D$ pot fi inserate in circuit. Astfel am aratat o cale practica de a mari lungimea circuitului pana cand epuizam toate nodurile.

Astfel pentru graful nostru vom determina componentele tari conexe, si vom cauta un circuit hamiltonean in cea mai mare dintre acestea. De acum ne vom concentra doar asupra nodurilor acestei componente. Evident ca aceasta componenta conexa contine cel putin un circuit, pentru a determina unul facem o cautare in adancime, si trebuie sa gasim la un moment dat o muchie de intoarcere (pentru ca altfel componenta nu ar fi tare conexa). Vom imparti nodurile din aceasta componenta in patru multimi: $A$ multimea nodurilor din circuit, $B$ multimea nodurilor din afara circuitului pentru care exista si arce orientate de la noduri din circuit la ele, si arce orientate de la ele la noduri din circuit, $C$ multimea nodurilor din afara circuitului pentru care exista numai arce ce pornesc din circuit inspre noduri, si $D$ multimea nodurilor pentru care toate arcele intre ele si noduri din circuit sunt orientate de la ele inspre circuit. Puteti observa ca nodurile din multimea $B$ pot fi inserate tot timpul in circuit undeva inlocuind un arc intre doua noduri ale circuitului cu doua arce de la un nod al circuitului la nodul multimii $B$ si apoi la alt nod din circuit. Inserarea unui astfel de nod dureaza maxim $O(n)$ pasi, alti $O(n)$ pasi ar fi necesari pentru modificarea multimilor $B, C, D$ pentru ca circuitul s-a schimbat. Dupa ce nu ne mai ramane nici un nod in $B$. Ramanem doar cu noduri de tip $C$ sau $D$. Orice nod din multimea $C$ va avea cel putin un arc orientat spre alt nod din multimea $D$ pentru ca altfel nu am fi intr-o componenta tare conexa. Acum aceste doua noduri legate printr-o muchie dinspre $C$ inspre $D$ pot fi inserate in circuit. Astfel am aratat o cale practica de a mari lungimea circuitului pana cand epuizam toate nodurile.

Daca folosim metoda de determinare a componentelor tari conexe folosind un algoritm eficient de complexitate $O(N + M)$, atunci algoritmul are complexitatea $O(N^2^)$ pentru ca la fiecare inserare facem $O(n)$ pasi. Un algoritm mai eficient nu putem obtine deoarece $M = N(N-1)/2$, deci si citirea datelor e $O(N^2^)$. N a fost fixat la $100$ pentru ca am vrut sa punem accent asupra ideii de gasire a circuitului si nu asupra algoritmului de determinare eficienta a componentelor tari conexe.
h2. TreiD