Fişierul intrare/ieşire:dfs.in, dfs.outSursăad-hoc
AutorArhiva EducationalaAdăugată degabitzish1Gabriel Bitis gabitzish1
Timp execuţie pe test0.2 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content