Inverseaza reviziile

Diferente pentru problema/dfs intre reviziile #22 si #1

Diferente intre titluri:

Parcurgere DFS - componente conexe

dfs

Diferente intre continut:

== include(page="template/taskheader" task_id="dfs") ==

Se da un graf neorientat cu $N$ noduri si $M$ muchii.
 
h2. Cerinta
 
Sa se determine numarul componentelor conexe ale grafului.

Poveste si cerinta...

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

Fisierul de intrare $dfs.in$ ...

h2. Date de iesire

In fisierul de iesire $dfs.out$ se va afisa numarul de componente conexe ale grafului.

In fisierul de iesire $dfs.out$ ...

h2. Restrictii

* $1 ≤ N ≤ 100 000$
* $0 ≤ M ≤ minim(200 000, N*(N+1)/2)$
* Pentru 50% dintre teste $1 ≤ N ≤ 1 000$

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. dfs.in |_. dfs.out |

| 6 3
1 2
1 4
3 5
| 3

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|

h2. Indicatii de rezolvare

h3. Explicatie

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':/infoarena.ro/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':/infoarena.ro/job_detail/153538?action=view-source.

...

== include(page="template/taskfooter" task_id="dfs") ==

Nu exista diferente intre securitate.

Diferente intre topic forum:

2788