Problema se rezolva prin parcurgeri DFS din fiecare nod nemarcat, si marcarea nodurilor in aceste parcurgeri. Algoritmul este explicat pe 'wikipedia':http://en.wikipedia.org/wiki/Depth-first_search si 'topcoder':http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=graphsDataStrucs2. O rezolvare care retine graful prin matricea de adiacenta va obtine doar 50 de puncte. Sursa bazata pe aceasta idee se gaseste 'aici':/job_detail/146224?action=view-source. O rezolvare care foloseste liste de vecini pentru retinerea grafului obtine 100 de puncte. Sursa ce obtine punctajul maxim e disponibila 'aici':/job_detail/146226?action=view-source.

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

== include(page="template/taskfooter" task_id="dfs") ==
==SmfTopic(topic_id="2788")==