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 muchii <tex>M \subset E</tex> cu proprietatea ca &forall; $i$ &isin; $V$ 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$).

Fie $G$ un graf bipartit. Numim *cuplaj* o submultime de muchii <tex>M \subset E</tex> cu proprietatea ca &forall; $i$ &isin; $V$ 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 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

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
 

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.
Bogdan: cosmine in primul rand nu terminasem problema. normal ca pun solutia smechera, doar am dat N < 2000 :). La flux1 si flux2 am vorbit si cu alti membri infoarena care mi-au sugerat sa fac in doua probleme. am inteles ca azi (03.03.2008) discutati arhiva educationala. daca se hotaraste ceva o sa schimb precum se decide.