Pentru orice $i$ din $A$ definim $R{~i~}$ ca fiind nodul de care este acesta cuplat in $B$. De asemenea, pentru orice nod $i$ din $B$, definim $L{~i~}$ ca fiind nodul de care este acesta cuplat in $A$. Initial, vectorii au valoarile $0$.
Pentru fiecare nod necuplat din $A$ apelam functia recursiva $pairup$ care va functiona astfel:

# daca exista un vecin necuplat de-ai lui $i$ ({$R{~i~} = 0$}), il vom cupla cu unul dintre ei;
# daca nu, incercam sa fortam cuplarea lui $i$ (daca se poate) cu un vecin deja cuplat (fie el $j$); deci, va trebui sa  recuplam nodul de care era anterior legat $j$ si vom apela recursiv functia $pairup$, de data aceasta pentru {$L{~j~}$}.

# daca exista un vecin necuplat de-ai lui $i$, il vom cupla cu unul dintre ei;
# daca nu, incercam sa fortam cuplarea lui $i$ (daca se poate) cu un vecin deja cuplat (fie el $j$); decuplandu-l pe $j$, va trebui sa recuplam nodul de care era anterior legat, deci vom apela recursiv functia $pairup$, de data aceasta pentru {$L{~j~}$}.

La final, valoarea *cuplajului maximal* va fi egala cu numarul de noduri $i$ cuplate, adica cele pentru care $R{~i~} > 0$.

h2. Probleme asemanatoare:

* "http://infoarena.ro/problema/java": Gandaci Java
* "http://acm.sgu.ru/problem.php?contest=0&problem=252": Railway Communication
* "http://acm.sgu.ru/problem.php?contest=0&problem=190": Dominoes

* "Gandaci Java":http://infoarena.ro/problema/java
* "Railway Communication":http://acm.sgu.ru/problem.php?contest=0&problem=252
* "Dominoes":http://acm.sgu.ru/problem.php?contest=0&problem=190

== include(page="template/taskfooter" task_id="cuplaj1") ==