Fișierul intrare/ieșire feisbuc.in, feisbuc.out Sursă Olimpiada locală 2015, clasele 11-12
Autor Radu Boriga Adăugată de avatar heracle Radu Muntean heracle
Timp de execuție pe test 0.1 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 emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

Feisbuc (clasele 11-12)

Cuprins de febra socializării on-line, Firicel a creat o nouă rețea de socializare, numită Feisbuc. În timp, între unele perechi de utilizatori ai rețelei s-au stabilit relații de prietenie reciprocă. Pentru a menține și dezvolta rețeaua Feisbuc, Firicel are nevoie de mai mulți bani, pe care s-a gândit să-i obțină din publicitate on-line. În acest sens, el a implementat în cadrul rețelei o mesagerie instantanee care îi permite să trimită un mesaj publicitar oricărui utilizator al rețelei într-o secundă. Din rațiuni de marketing, Firicel nu dorește să trimită el însuși mesaje publicitare tuturor utilizatorilor rețelei și, ca atare, sistemul de mesagerie instantanee creat va trimite, în mod automat, orice mesaj publicitar primit de către un utilizator și tuturor prietenilor acestuia, tot într-o secundă. În plus, în rețeaua Feisbuc, prieteniile au fost limitate astfel încât, niciun utilizator să nu primească un mesaj publicitar de mai multe ori (nici simultan, nici în secunde diferite).

Cunoscând perechile de utilizatori între care s-au stabilit relații de prietenie reciprocă, scrieți un program care să determine:
a) numărul minim de utilizatori u cărora Firicel trebuie să le transmită un mesaj publicitar astfel încât respectivul mesaj să fie primit de toți utilizatorii rețelei Feisbuc;
b) timpul minim t în care toți utilizatorii rețelei Feisbuc primesc mesajul publicitar trimis de Firicel.

Date de intrare

Fișierul de intrare feisbuc.in conține pe prima linie două numere naturale nenule n și m, primul reprezentând numărul utilizatorilor rețelei Feisbuc, identificați prin numere naturale cuprinse între 1 și n, iar cel de-al doilea reprezentând numărul perechilor de utilizatori ai rețelei între care s-au stabilit relații de prietenie reciprocă. Pe următoarele m linii din fișier sunt scrise perechi de numere naturale de forma X Y, indicând faptul că utilizatorii X și Y sunt prieteni.

Date de ieșire

Pe prima linie a fișierului de ieșire feisbuc.out se vor scrie cele două numere naturale u și t cerute, despărțite printr-un spațiu.

Restricții

1 <= n <= 5000
1 <= m <= 1000000
1 <= X < Y <= n
Perechile X Y sunt distincte și respectă restricțiile de prietenie impuse de rețea.
Pentru 50% din teste se garantează faptul că 1 <= n <= 500 și 1 <= m <= 100000.
Pentru determinarea corectă a numărului u se acordă 30% din punctajul testului respectiv, iar pentru determinarea corectă a numărului t se acordă 70% din punctajul testului respectiv.

Exemplu

feisbuc.in feisbuc.out
8 6
1 2
2 4
2 5
3 7
4 8
6 7
2 3

Explicație

Pentru ca un mesaj publicitar să fie primit de toți utilizatorii rețelei, Firicel trebuie să-l trimită unuia dintre utilizatorii 1, 2, 4, 5, 8 și unuia dintre utilizatorii 3, 6, 7, deci u=2.

Timpul minim în care toți utilizatorii rețelei primesc mesajul publicitar trimis de Firicel este t=3 secunde și se obține, de exemplu, dacă Firicel transmite mesajul publicitar utilizatorilor 2 și 7 într-o secundă, de la aceștia se transmite mesajul la 1, 5, 4 și respectiv 3 și 6 în secunda a doua, iar în secunda a treia, de la utilizatorul 4 se transmite mesajul la utilizatorul 8.

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

Indicii de rezolvare

Arată 4 categorii