Fişierul intrare/ieşire:rmvc.in, rmvc.outSursăAlgoritmiada 2013, Runda Finala
AutorCosmin Silvestru NegruseriAdăugată deklamathixMihai Calancea klamathix
Timp execuţie pe test0.3 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Return of the MVC

Finalizăm trilogia MVC de anul acesta prin următoarea problemă: Fie un graf G cu N noduri şi M muchii. Numim acoperire cu noduri a grafului o mulţime de noduri A cu proprietatea că orice muchie din graf are cel puţin unul din capete situat in mulţimea A. În această problemă trebuie să găsiţi o acoperire cu noduri a grafului G de cardinal minim.

Se garantează ca pentru grafurile date în input, există o acoperire de noduri cu dimensiune maxim 18.

Date de intrare

Fişierul de intrare rmvc.in conţine pe prima sa linie numerele N şi M semnificând numărul de noduri şi numărul de muchii ale grafului. Următoarele M muchii conţin câte o pereche x y semnificând că există o muchie între nodul x şi nodul y. Se garantează că nu există muchii cu capetele în acelaşi nod, însă pot exista muchii duble.

Date de ieşire

Prima linie a fişierului rmvc.out va conţine dimensiunea acoperirii găsite. Cea de a doua linie va conţine nodurile din acoperire afişate în orice ordine. Orice soluţie de cardinal minim este acceptată.

Restricţii

  • 1 ≤ N ≤ 90
  • 1 ≤ M ≤ 320

Exemplu

rmvc.inrmvc.out
5 6
1 2
1 3
1 4
2 3
2 4
3 4
3
3 4 2
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?