Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2008-03-01 10:45:50.
Revizia anterioară Revizia următoare
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 din cate componente conexe este alcatuit graful.
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 ≤ 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
Trebuie sa te autentifici pentru a trimite solutii. Click aici
