==include(page="acm-icpc-upb-2008/solutii/g2mm")==

In primul rand trebuie mentionat faptul ca va exista intotdeauna un cuplaj perfect in acest graf, lucru care va reiesi din algoritmul prezentat in continuare. Vom nota graful din intrare cu G iar graful patrat cu @G^2@. Vom creea un arbore partial al grafului G, pentru asta putem folosi un DF sau un BF. Avand arborele il vom parcurge de jos in sus (de la frunze catre radacina) si vom creea cuplajul astfel: Pentru fiecare nod consideram sirul F{~1~}, F{~2~}, F{~3~} .. F{~N~} unde F{~i~} este un fiu al nodului curent care nu a fost inca introdus in cuplaj. Daca acest sir are numar impar de noduri atunci introducem si nodul curent in sir, acesta avand acum un numar par de elemente. Acum cuplam pur si simplu aceste noduri din sir (e usor de gasit o astfel de modalitate) avand in vedere ca in @G^2@ aceste noduri vor avea toate muchii intre ele. Exista intotdeauna solutie deoarece graful are un numar par de noduri si este conex.
 

==include(page="acm-icpc-upb-2008/solutii/ksecv")==
==include(page="acm-icpc-upb-2008/solutii/maxunice")==