Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2008-03-01 16:53:05.
Revizia anterioară Revizia următoare
Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | cuplaj1.in, cuplaj1.out | Sursă | |
| Autor | Autor necunoscut | Adăugată de |  Bogdan-Alexandru Stoica •fireatmyself |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Cuplaj Maxim
Fie un graf neorientat G=(V,E) cu N noduri si M muchii. Numim cuplaj o submultime de muchii 
cu proprietatea ca ∀ i ∈ V exista cel mult un j ∈ 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| ≥ |A| (unde cu | | am notat cardinalul unei multimi).
Date de intrare
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.
Date de iesire
In fisierul de iesire cuplaj1.out se va scrie o singura valoare, cardinalul cuplajului maxim.
Restrictii
- 1 ≤ N ≤ 1000
- 1 ≤ M ≤ N*(N-1)/2
Exemplu
| cuplaj1.in | cuplaj1.out |
|---|---|
| 8 9 1 2 2 3 3 4 2 4 3 8 4 5 2 5 8 5 2 7 | 3 |
Indicatii
...
Trebuie sa te autentifici pentru a trimite solutii. Click aici
