| Fişierul intrare/ieşire: | dirty.in, dirty.out | Sursă | Cerc informatică Vianu |
| Autor | Catalin Francu | Adăugată de |  Catalin Francu •Catalin.Francu |
| Timp execuţie pe test | 0.4 sec | Limită de memorie | 8192 kbytes |
| Scorul tău | N/A | Dificultate |   4/5 |
Poti vedea testele pentru aceasta problema accesand atasamentele.Dirty
NSA a înfiinţat Departamentul pentru Interceptarea Reţelelor Teroriste pe Yahoo, Facebook, Apple, Google şi Skype (NSA PRISM). Departamentul veghează la liniştea noastră, a muritorilor simpli fără nimic de ascuns, şi analizează datele obţinute folosind o reţea de calcul formată din calculatoare conectate prin cabluri bidirecţionale. Fiecare cablu leagă exact două calculatoare, dar un calculator poate avea mai multe cabluri. Oricare două calculatoare sunt legate direct prin cel mult un cablu. În prezent, reţeaua este conexă, adică oricare două calculatoare pot comunica, direct sau indirect.
Anarhista Julianna Sage şi-a folosit puterea de seducţie pentru a îl convinge pe tehnicianul Steward Noden să-i ofere un tur al laboratorului. În realitate, ea ţine pe stick un virus cu care poate distruge orice calculator din reţea. Pentru a sabota cât mai mult reţeaua, Julianna doreşte să viruseze acel calculator prin dispariţia căruia reţeaua se fragmentează în cât mai multe sub-reţele deconectate una de alta. Cunoscând structura reţelei, ajutaţi-o pe Julianna să afle toate variantele de atac pe care le are.
Date de intrare
Fişierul de intrare dirty.in conţine, pe prima linie, numărul N de calculatoare şi numărul M de cabluri. Pe următoarele M linii sunt indicate conexiunile, sub forma câte unei perechi X Y cu semnificaţia că există un cablu între calculatoarele numerotate X şi Y.
Date de ieşire
În fişierul de ieşire dirty.out se vor scrie, pe prima linie, R = numărul de sub-reţele în care poate fragmenta Julianna reţeaua şi V = numărul de variante de a sabota un calculator pe care le are ea. Pe a doua linie se vor scrie cele V numere de ordine ale acestor calculatoare, în ordine crescătoare şi despărţite prin spaţii.
Restricţii
- 1 ≤ N ≤ 100.000
- 1 ≤ M ≤ 300.000
- 1 ≤ X, Y ≤ N
- Julianna garantează că există un calculator prin dispariţia căruia reţeaua să se fragmenteze.
Exemplu
| dirty.in | dirty.out | poză |
|---|---|---|
| 9 10 1 2 3 1 2 3 6 7 8 6 6 3 3 4 5 3 8 9 4 5 | 3 2 3 6 | 
|
Explicaţie
Prin sabotarea calculatorului 3, reţeaua se fragmentează în 3 sub-reţele: { 1, 2 }, { 4, 5 } şi { 6, 7, 8, 9 }.
Prin sabotarea calculatorului 6, reţeaua se fragmentează în 3 sub-reţele: { 1, 2, 3, 4, 5 }, { 7 } şi { 8, 9 }.
Sabotarea calculatorului 8 fragmentează reţeaua în numai două componente, iar sabotarea altor calculatoare nu fragmentează reţeaua.
