----------------------------------
| PROBLEMA 1: Retele de telefonie |
| PUNCTAJ: 60 Dexteri |
| DEADLINE: Joi, 4 februarie |
| TIMP DE IMPLEMENTARE: 70 minute |
| COMPLEXITATE RECOMANDATA: O(n+l),|
| unde l este nr. de linii|
| din fisierul de intrare.|
| TIMP DE EXECUTIE: 1 sec/test |
| pe Pentium 166Mhz |
----------------------------------
Intr-un oras exista n abonati si mai multe retele de telefonie. Se stie
ca doi abonati apartin aceleasi retele de telefonie daca primul abonat il
poate contacta pe cel de-al doilea (direct sau prin intermediul altor abonati)
si reciproc. Problema consta in determinarea tuturor retelelor de telefonie,
prin specificarea abonatilor fiecarei retele.
Datele de intrare se citesc din fisierul "abonat.in" care are urmatoarea
forma:
- prima linie contine n, numarul de abonati (n<=10000)
- urmatoarele linii vor contine fiecare doua numere A si B, separate
prin cate un spatiu, indicand faptul ca abonatul A il poate contacta
direct pe abonatul B (fapt din care NU rezulta ca abonatul B il poate
contacta direct pe abonatul A).
Numarul de linii din fisierul de intrare nu va depasi 25000.
Fisierul de iesire "abonat.out" va contine pe fiecare linie membrii
unei retele de telefonie. In cadrul fiecarei retele, membrii acesteia vor
fi afisati in ordine crescatoare. Retelele vor fi si ele afisate in ordine
crescatoare, in functie de abonatul cu numarul de ordine cel mai mic din
fiecare retea.
Exemplu:
abonat.in abonat.out
--------- ----------
10 1 7 9
2 3 2 3
3 2 4 5 6 10
3 1 8
1 9
9 7
7 1
4 3
4 10
6 10
5 4
5 6
10 5
5 8
5 7
|
|
