| 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.
