Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | dfs.in, dfs.out | Sursă | ad-hoc |
| Autor | Arhiva Educationala | Adăugată de |  Gabriel Bitis •gabitzish1 |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 524288 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Poti vedea testele pentru aceasta problema accesand atasamentele.Vezi solutiile trimise | Statistici
Parcurgere DFS - componente conexe
Se da un graf neorientat cu N noduri si M muchii.
Cerinta
Sa se determine numarul componentelor conexe ale grafului.
Date de intrare
Fisierul de intrare dfs.in contine pe prima linie numerele N si M cu semnificatia din enunt, iar pe urmatoarele M linii se gasesc cate doua numere X si Y cu semnificatia: exista muchie de la nodul X la nodul Y.
Date de iesire
In fisierul de iesire dfs.out se va afisa numarul de componente conexe ale grafului.
Restrictii
- 1 ≤ N ≤ 100 000
- 0 ≤ M ≤ minim(200 000, N*(N+1)/2)
- Pentru 50% dintre teste 1 ≤ N ≤ 1 000
Exemplu
| dfs.in | dfs.out |
|---|---|
| 6 3 1 2 1 4 3 5 | 3 |
Indicatii de rezolvare
Problema se rezolva prin parcurgeri DFS din fiecare nod nemarcat, si marcarea nodurilor in aceste parcurgeri. Algoritmul este explicat pe wikipedia si topcoder. O rezolvare care retine graful prin matricea de adiacenta va obtine doar 50 de puncte. Sursa bazata pe aceasta idee se gaseste aici. O rezolvare care foloseste liste de vecini pentru retinerea grafului obtine 100 de puncte. Sursa ce obtine punctajul maxim e disponibila aici.
Cosmin: Gabriel ai pus si un test cu un lant lung? S-ar putea sa iasa din stiva un asemenea test pentru implementarea recursiva si vrei sa fi sigur ca implementarea ta merge pe orice test. Daca nu ai un astfel de test te rog adauga unul unde lantul arata asa 1 - 2 - 3 ... - 100 000 si reevalueaza sursele, s-ar putea sa pice cateva.
