h1(#autobuze). 'Autobuze':problema/autobuze

Solutii prezentate de ==user(user="Teodor94" type="tiny")==.
 

h4. $Solutia 1: O(N^2^) - 50 puncte$
Vom considera ca cele $N$ numere sunt nodurile unui graf neorientat, iar fiecare nod $i$ o sa aiba valoarea $a[i]$. Initial, graful are $N$ noduri si $0$ muchii. Pentru fiecare nod $i$ de la $1$ la $N$, vom parcurge toate celelalte $N$ noduri, iar cand gasim un nod $j$ care are proprietatea ca $a[i]$ divide $a[j]$ sau viceversa, vom trage o muchie intre aceste doua noduri $i$ si $j$. In momentul acesta, problema se reduce la gasirea numarului de componente conexe existente in acest graf. Acest lucru se poate face liniar cu o parcurgere in adancime / latime.