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

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.

Wefgef: Pe infoarena nu este limitata stiva ca pe .campion la 1 mega. Cat timp intra in 8 mega si in limita de memorie impusa de problema, va lua 100. Teoretic, rezolvarea recursiva ar trebui sa intre fara probleme pentru 100.000 de noduri.

Cum se trimit solutii?