cuplaj1

Cuplaj Maxim

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

Poveste si cerinta...

== include(page="template/taskheader" task_id="cuplaj1") ==
 
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| $ge; |A|$.

h2. Date de intrare

Fisierul de intrare $cuplaj1.in$ ...

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

In fisierul de iesire $cuplaj1.out$ ...

In fisierul de iesire $cuplaj1.out$ se va scrie o singura valoare, cardinalul cuplajului maxim.

h2. Restrictii

* $... ≤ ... ≤ ...$

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

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

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

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

|

h3. Explicatie

h3. Indicatii

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

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