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

h3. Definitie
 
Se numeste *graf bipartit* un graf $G$ ale carui noduri pot fi partitionate in doua multimi dijscunte $A$ si $B$ care au umratoarele proprietati:
 
# ∀ $i$, $j$ ∈ $A$ nu exista muchie intre $i$ si $j$
# ∀ $i$, $j$ ∈ $B$ nu exista muchie intre $i$ si $j$
# ∀ $i$ ∈ $A$ ∃ $j$ ∈ $B$ astfel incat intre $i$ si $j$ sa fie muchie
 
h3. Problema
 
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 nico alta multime $M'$ cu $|M'| &gt; |M|$ (unde cu $|M|$ am notat cardinalul multimii $M$).
 
h3. Cerinta
 
Se da un graf bipartit $G$. Se cere sa se gaseasca valoarea cuplajului maxim.

Fie un graf neorientat $G=(V,E)$ cu $N$ noduri si $M$ muchii. Numim *cuplaj* o submultime de muchii <tex>A \subseteq E</tex> cu proprietatea ca &forall; $i$ &isin; $V$ exista cel mult un $j$ &isin; $A$ astfel incat sa existe muchie intre $i$ si $j$. Un *cuplaj maxim* este un cuplaj de cardinal maxim, adica nu exista niciun alt cuplaj $B$ cu $|B| &gt; |A|$ (unde cu $| |$ am notat cardinalul unei multimi).

h2. Date de intrare

Pe prima linie a fisierului de intrare $cuplaj1.in$ se afla $N1$, $N2$ si $M$. $N1$ reprezinta numarul de noduri ale multimii $A$, iar $N2$ numarul de noduri ale multii $B$. Pe urmatoarele $M$ linii se afla cate doua numere $a$ si $b$ cu semnificatia ca intre nodurile $a$ ∈ $A$ si $b$ ∈ $B$ exista muchie.

Pe prima linie a fisierului de intrare $cuplaj1.in$ se afla $N$ si $M$. Pe urmatoarele $M$ linii se afla cate doua numere $a$ si $b$ cu semnificatia ca nodurile $a$ si $b$ sunt adiacente.

h2. Date de iesire

h2. Restrictii

* $1 ≤ N1, N2 ≤ 1000$
* $1 ≤ M ≤ (N1+N2)*(N1+N2-1)/2$
* nodurile multimii $A$ sunt numerotate de la $1$ la $N1$
* nodurile multimii $B$ sunt numerotate de la $1$ la $N2$

* $1 ≤ N ≤ 1000$
* $1 ≤ M ≤ N*(N-1)/2$

h2. Exemplu
table(example). |_. cuplaj1.in |_. cuplaj1.out |

| 5 4 6
1 1
2 1
1 4
3 2
5 4
4 2

| 8 9
1 2
2 3
3 4
2 4
3 8
4 5
2 5
8 5
2 7

| 3
|
h3. Indicatii

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'$.
 
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.

...

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