Fișierul intrare/ieșire dirty.in, dirty.out Sursă Cerc informatică Vianu
Autor Cătălin Frâncu Adăugată de avatar Catalin.Francu 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 stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 6 categorii