034 Ciclu Eulerian

[•pauldb]

Aici puteti discuta despre problema Ciclu eulerian din Arhiva educationala.

[•andrei-alpha]

Prima din figurile alea nu cred ca are vreun ciclu eulerian ca sunt 4 noduri cu grad impar si unul cu grad par
 

[•gabor_oliviu1991]

in exemplul problemei, avem muchie de la 2 la 2? defapt ramanem pe nodul 2 ? sau nu am inteles eu bine.

[•wefgef]

Da, grafurile pot contine muchii multiple intre 2 noduri sau self-loops.

[•mariusdrg]

Ar mai fi inca o metoda usoara si demna de mentionat care are in componenta un singur dfs. O astfel de solutie se poate vedea aici: http://infoarena.ro/job_detail/263481. Aceasta ia doar 50 de puncte din cazua ca foloseste un dfs(intrece marimea stivei din cate observ) dar e usor de inteles ce face si usor de implementat. Practic ceea ce face sursa mea e: fac un dfs prin tot graful si am un vector de vizitat pe muchii(nu pe noduri), In data ce nu mai pot merge nicaieri tiparesc nodul.

P.S. Scuza-ti implementarea urata , dar e facuta in borland(vine oji.....).

[•amadaeus]

fac un dfs prin tot graful si am un vector de vizitat pe muchii(nu pe noduri), In data ce nu mai pot merge nicaieri tiparesc nodul.

Algoritmul este practic acelasi: construiesc un ciclu si ma intorc pe el, intercaland toate ciclurile suplimentare. Implementarea este putin diferita (marcajele pe muchii) si merita mentionata intr-adevar ca si alternativa; ar fi ideal insa daca ai implementa si o varianta nerecursiva folosind aceeasi idee, pentru a avea o sursa de 100p, care se poate incadra in articolul de solutii.

[•stocarul]

Am implementat eu un dfs nerecursiv pt problema asta...
http://infoarena.ro/job_detail/264061
Insa din pacate nu intra in timp pe testele 8 si 10

L.E.: am facut o mica modificare si am luat suta 

[•andr33a]

Daca exista un ciclu eulerian pt o parte din noduri, iar restu` nodurilor sunt izolate, se afiseaza ciclu` sau -1? 

[•andrei-alpha]

-1 Ciclul trebuie sa fie pentru toate nodurile.

[•pauldb]

-1 Ciclul trebuie sa fie pentru toate nodurile.

Nu. Ciclul trebuie sa traverseze toate muchiile o singura data si nu are nici o restrictie privind nodurile. Daca exista noduri izolate, acestea nu intra in calcul.

[•wefgef]

Eu cred ca enuntul problemei ar trebui revizuit.

Un graf se numeste eulerian daca si numai daca este conex si gradul fiecarei nod este par.

[•amadaeus]

Eu cred ca enuntul problemei ar trebui revizuit.

Un graf se numeste eulerian daca si numai daca este conex si gradul fiecarei nod este par.

Se poate discuta mult pe marginea definitiei; fiecare autor al unei lucrari de teoria grafurilor are particularitatile sale in definitii sau notatii. In cazul de fata, imi pare irelevanta orice obiectie, existand o corespondenta biunivoca intre multimea grafurilor care admit un ciclu eulerian si multimea grafurilor conexe ale caror noduri au toate gradele pare (este una dintre teoremele lui Euler).

Din considerente practice, mi se pare ca a defini grafurile euleriene ca fiind acele grafuri cu proprietatea P1, si a demonstra apoi ca ele au (necesar si suficient) proprietatea P2, este acelasi lucru cu a interschimba P1 si P2 in fraza anterioara. Din considerente teoretice, diferenta aceasta poate deveni importanta, insa, asa cum am spus, lucrarile de specialitate jongleaza prea mult cu termenii pentru a putea avea pretentia unei singure notatii corecte; in final, ramane doar o problema de terminologie.

[•razyelx]

imi explicati si mie va rog "La fiecare pas in construirea ciclului, vom alege intotdeauna muchiile de intoarcere inaintea muchiilor de arbore." . Muchiile de intoarcere is alea care formeaza ciclu? Si alea de arbore care nu formeaza? De unde imi pot da seama care muchii is care? Explicatie e putin succinta.
 

[•Florian]

Acolo se refera la arborele DFS. Atunci cand faci parcurgerea normala DFS(), se creaza de fapt un arbore. Sa luam algoritmul concret:

Cod:

void dfs(int x)
 {
    viz[x] = 1;
    pt fiecare vecin a lui x
      { 
          if(viz[vecin] == 0) dfs(vecin); // asta este muchie de arbore
          else ; // => viz[vecin]=1 => muchia (x, vecin) este muchie de intoarcere si inchide un ciclu
       }
  }

Ia-ti un graf pe hartie si deseneaza-ti nodurile si muchiile exact in ordinea parcurgerii DF, si o sa intelegi cum sta treaba. Succes! 

[•otilia_s]

Eu am rezolvat problema fara sa utilizez STL, alocand cu realloc , dar obtin SIGSEGV pe 3 teste.  Nu inteleg de ce, pentru ca am folosit aceeasi metoda ca si in rezolvarea oficiala, deci ar trebui sa foloseasca la fel de multa memorie.
Puteti sa va uitati si pe sursa mea, va rog: http://infoarena.ro/job_detail/295583?action=view-source
Multumesc! 

[•andrei-alpha]

Inserează citat
Eu am rezolvat problema fara sa utilizez STL, alocand cu realloc , dar obtin SIGSEGV pe 3 teste.  Nu inteleg de ce, pentru ca am folosit aceeasi metoda ca si in rezolvarea oficiala, deci ar trebui sa foloseasca la fel de multa memorie.
Puteti sa va uitati si pe sursa mea, va rog: http://infoarena.ro/job_detail/295583?action=view-source
Multumesc!  Smile

Poti sa iei testele de la atasamente,  le rulezi la tine si vezi exact unde crapa. 

[•Procopliuc]

De ce-mi da killed by signal daca folosesc liste liniare? 
Pe windows la primul test de la atasamente imi merge bine,iar la evaluare imi da killed by signal

[•Florian]

scanf ("%i%i",&x,&y); 

Incearca sa citesti cu " %d ". Poate de aici e. Daca nu, fii atent cum faci legaturile alea. E destul de dubioasa sursa ta. Nu vad unde simulezi stiva, si mi se pare ciudat ca aloci noduri noi (apoi le stergi) de fiecare data cand apelezi ciclu() . Si un sfat prietenesc: ordoneaza-ti putin sursele (ca aspect), ca asa nu intelege nimeni nimic.  Spor!

[•marcelcodrea]

Linux are o gestiune impecabilă a memoriei, spre deosebire de Windows unde în cazul în care scăparea nu este foarte mare, execuţia o să pară în regulă şi o să întoarcă 0. De aceea nu apare nimic suspect când rulezi de acasă. Primeşti "Killed by signal" cel mai probabil din cauza unor greşeli la operaţiile cu liste, accesezi ceva nealocat în prealabil. Pentru a spori lizibilitatea surselor (aşa cum ai structurat-o, sursa e indescifrabilă pentru oricine care nu a scris-o, adică pentru noi toţi), poţi folosi CodeBlocks care oferă posibilitatea indentării lor urmând un anumit tipar printr-un singur click.

[•Procopliuc]

cred ca  sursa http://infoarena.ro/job_detail/313322?action=view-source  este structurata putin mai bine

[•devilkind]

Te inseli . Uita-te si tu la sursele celorlalti concurenti si vezi cum au implementat .

[•Procopliuc]

care-i greseala?
Pe windows imi merge bine

[•popoiu.george]

Iau 80 pct, iar pe testele 2 si 4 iau "fisier de iesire corupt!" si nu inteleg de la ce ar putea fi.

Stie cineva? 

[•pauldb]

M-am uitat in evaluator si acest mesaj apare cand ce afisezi nu respecta formatul cerut. Ori afisezi prea multe/prea putine noduri ori afisezi varfuri care nu apartin intervalului [1, N] (in situatia in care exista solutie).

[•APOCALYPTO]

Salut! Am si eu o intrebare.
Ciclul eulerian nu iese din prima decat in cazul in care noduri critice?
              (cum e in exemplul de mai sus nodul 3 )
a iesit din prima= apelam doar o data functia euler si avem raspunsul