Se numeste *graf bipartit* un graf $G$ ale carui noduri pot fi partitionate in doua multimi disjuncte $A$ si $B$ astfel incat oricare muchie uneste un nod din $A$ si un nod din $B$. Cu alte cuvinte, nu exista doua nuduri $i$ si $j$ din aceeasi multime astfel incat sa existe muchie intre ele.

Fie $G$ un graf bipartit. Numim *cuplaj* o submultime de noduri <tex>M \subset A</tex> cu proprietatea ca &forall; $i$ &isin; $M$ exista un unic $j$ &isin; $B$ astfel incat intre $i$ si $j$ sa fie muchie. Numim *cuplaj maxim* o multime $M$ de cardinal maxim, adica nu exista nicio alta multime $M'$ cu $|M'| &gt; |M|$ (unde cu $|M|$ am notat cardinalul multimii $M$).

Fie $G$ un graf bipartit. Numim *cuplaj* o submultime de muchii <tex>M \subset E</tex> (unde $E$ este multimea muchiilor grafului) cu proprietatea ca &forall; $i$ &isin; $A$ exista cel mult o muchie in $M$ incidenta in $i$. Spunem ca $i$ este *cuplat* de cuplajul $M$ daca exista o muchie in $M$ incidenta in $i$. In caz contrar spunem ca $i$ este *necuplat*. Numim *cuplaj maxim* o multime $M$ de cardinal maxim, adica nu exista nicio alta multime $M'$ cu $|M'| &gt; |M|$ (unde cu $|M|$ am notat cardinalul multimii $M$).

h2. Cerinta

h2. Restrictii

* $1 ≤ N1, N2 ≤ 1000$
* $1 ≤ M ≤ 200 000$

* $1 ≤ N1, N2 ≤ 2000$
* $1 ≤ M ≤ 310 000$

* nodurile multimii $A$ sunt numerotate de la $1$ la $N1$
* nodurile multimii $B$ sunt numerotate de la $1$ la $N2$

O metoda de rezolvare foloseste algoritmii de flux maxim:
Se construieste un graf $G'$ pornind de la graful $G$ la care mai adaugam doua noduri: o sursa si o destinatie. Toate nodurile multimii $A$ se leaga de sursa respectiva si toate nodurile multimii $B$ se leaga de destinatia respectiva. Se considera ca muchiile grafului $G'$ au capacitatea $1$. Valoarea cuplajului maxim in graful $G$ este numeric egala cu valoarea fluxlui maxim din graful $G'$.

O solutie mai rapida si mult mai usor de implementat este cea care se bazeaza pe lanturi augmentative:
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$, 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$.
 
Pentru clarificarea algoritmului puteti consulata "sursa":http://infoarena.ro/job_detail/186901?action=view-source.
 

Mai multe detalii despre *cuplajul in graf bipartit*, precum si probleme asemanatoare se pot gasi in acest "aritcol":http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlow2.

h2. Probleme asemanatoare:
 
* "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") ==