014 Parcurgere DFS - componente conexe

[•filipb]

Aici puteti discuta despre problema Parcurgere DFS - componente conexe.

[•petre]

de ce la testul 17 e raspuns 2?

[•gabitzish1]

Pai o explicatie stiintifica nu pot sa'ti dau, dar daca s'au luat punctaje de 100, pe aceleasi teste pe care ai luat tu 95, inseamna ca la testul 17 chiar sunt 2 componente conexe, de'aia raspunsul e 2.
Componentele sunt fomate din nodurile de la 1 la 99997 respectiv de la 99998 la 100000.

[•petre]

oricum testul 17 e gresit:
sunt 100000 de muchii,iar fisierul de intrare are 99999

[•wefgef]

Am modificat testul 17 si am reevaluat .

[•Mishu91]

Am si eu o intrebare... stiu ca e putin ciudata, da' limba romana nu e punctu' meu forte Ce inseamna componente conexe?

[•filipb]

O componenta conexa intr-un graf neorientat este o submultime maximala C a multimii de noduri astfel incat oricare ar fi doua noduri x si y din C, exista drum de la x la y si de la y la x.
Google it. In plus, uita-te pe sursele din arhiva si ai sa vezi cum functioneaza algoritmul de determinare a componentelor astea.

[•Mishu91]

Mersi fain. Am inteles

[•zbarni]

Este DFS mai rapid decat BFS , sau este numai legat de testele acestea? cu al doilea am luat 60 de puncte.

[•razyelx]

DFS are aceeasi complexitate cu BFS: O(n+m).

[•toni2007]

E adevarat, doar ca una este recursiva iar cealalta iterativa, de aici diferenta de timp. Probabil ca ai folosit STL la bfs, care merge mai incet ca stiva (sa ma corecteze cineva daca gresesc), sau la bfs ai bagat de mai multe ori nodurile in coada ,

[•razyelx]

Se poate DFS si iterativ. Si ma chinui acum sa il implementez, dar nu am alte idei decat sa imi creez o stiva care sa o inlocuiasca pe cea din sistem pt functii. A facut careva interativ DFS?

[•Florian]

dar nu am alte idei decat sa imi creez o stiva care sa o inlocuiasca pe cea din sistem pt functii.

Pai altfel nu ai cum.  Iti retii in stiva nodurile, in ordinea parcurgerii. Atunci cand nu mai ai unde sa mergi din nodul st[vf], stergi varful stivei (--vf), si incerci noul varf (ii parcurgi vecinii). Repeti procedeul pana cand stiva devine vida. Uite un pseudocod:

Cod:

- introduc in stiva nodul de start
- cat timp am elemente in stiva: 
   -- daca nodul din varful stivei are un vecin nevizitat atunci
        ---vizitez vecinul. [ viz[nod] = 1; ]
        ---introduc in stiva vecinul. [ st[++vf] = nod;
   --altfel, scot din stiva nodul din varf. [ --vf ].
-

Implementarea e simpla! Succes!

[•frumushel]

am facut-o cu liste si merge viss...

[•alexandru92]

Pai altfel nu ai cum. 

Merge si recursiv ,sursa  oficiala  e facuta recursiv

[•Florian]

Postul tau e cam degeaba.  Daca ai fi citit cu atentie, ti-ai fi dat seama ca ma refeream la cum poate sa faca iterativ. Adica sa transforme algoritmul recursiv in iterativ, prin simularea stivei. Prin "altfel nu ai cum" ma refeream la faptul ca simularea stivei e obligatorie pentru a face iterativ.

[•Bit_Master]

Eu am facut cu matrice de adiacenta si am luat 100.

[•gabitzish1]

Tu ai liste de vecini, nu matrice de adiacenta.
Matricea de adiacenta e o matrice A de dimensiune N x N, unde A[ i ][ j ] = 1 daca exista muchie de la nodul i la nodul j, sau A[ i ][ j ] = 0 in caz contrar.

[•bogdanduduman]

Eu iau de la testu 12-20 - Killed by signal 11. imi poate spune cnv unde e 'problema' pe solutia trimisa?

[•blasterz]

Eu iau de la testu 12-20 - Killed by signal 11. imi poate spune cnv unde e 'problema' pe solutia trimisa?

Vezi ca limita e 1 <= N <= 100 000 !!! (tu ai declarat vectorii de 10 005 )

[•lady]

imi poate spune cineva, va rog, ce inseamna eroarea "Non-zero exit status." in borderoul de evaluare ? 
multumesc..

[•PlayLikeNeverB4]

Cod:

1 ≤ N ≤ 100 000

Tu ai declarat o matrice [0..100,0..100], deci dupa ce citesti (de exemplu) 101 incerci sa accesezi o zona de memorie nealocata.
Va trebui sa retii matricea sub forma de liste de adiacenta.

[•alexandru93]

salutare!...
am si eu o problema...trimit sursa si iau doar 15 pct:-? si pe restul testelor "incorect"...dar oricate teste as da eu...imi da ok! daca are cineva timp sa se uite pe sursa...poate vede greseala pe care nu o vad eu:-?
adresa e: http://infoarena.ro/job_detail/544998


am rezolvat...multumesc oricum

Nu posta consecutiv pe aceeasi tema. Editeaza-ti mesajele anterioare!

[•danalex97]

Si ... de unde as putea invata cum se lucreaza cu pointeri ?

[•Schumi]

http://zanasi.chem.unisa.it/download/C.pdf -> aceasta carte contine tot ce iti trebuie despre limbajul C. Capitolul 5 este dedicat pointerilor  
Vezi ca la problema asta poti sa eviti folosirea pointerilor. Iti poti tine un vector din stl cu vecinii fiecarui nod