Fișierul intrare/ieșire | dirty.in, dirty.out | Sursă | Cerc informatică Vianu |
---|---|---|---|
Autor | Cătălin Frâncu | Adăugată de | Cătălin Frâncu • Catalin.Francu |
Timp de execuție pe test | 0.4 sec | Limită de memorie | 8192 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
Dirty
NSA a înființat Departamentul pentru Interceptarea Rețelelor Teroriste pe Yahoo, Facebook, Apple, Google și Skype (DIRTYFAGS, numit colocvial și 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.