infoarena

Aici puteti discuta despre problema Ciclu eulerian (http://infoarena.ro/problema/ciclueuler) din Arhiva educationala (http://infoarena.ro/arhiva-educationala).

Prima din figurile alea nu cred ca are vreun ciclu eulerian ca sunt 4 noduri cu grad impar si unul cu grad par :-k
 (http://infoarena.ro/problema/ciclueuler?action-download&file=euler01.png&safe_only=true)

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

Da, grafurile pot contine muchii multiple intre 2 noduri sau self-loops (http://en.wikipedia.org/wiki/Loop_(graph_theory)).

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

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. ;)

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  :yahoo:

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

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

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.

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.
 

Acolo se refera la arborele DFS. Atunci cand faci parcurgerea normala DFS(), se creaza de fapt un arbore. Sa luam algoritmul concret:
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!  :)

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!  :)

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

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

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!

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  (http://www.codeblocks.org/downloads)care oferă posibilitatea indentării lor urmând un anumit tipar printr-un singur click.

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

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

care-i greseala? :-k
Pe windows imi merge bine ](*,)

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?  :-k

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

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

Nu inteleg ce vrei sa spui. Poti sa reformulezi intrebarea?

Ok! Ma refer la ultima varianta de rezolvare, cea cu ciclurile disjuncte.
Daca o sa te uiti in sursa lui Lucian vei observa ca dupa ce determina daca graful este eulerian e face un do-while in care cauta  ciclurile disjuncte din graf.
Un ciclu il gaseste dupa ce apeleaza o singura data functia euler();
Si eu ma intrebam daca avem nevoie de mai mult de un apel doar atunci cand avem deaface cu noduri critice?(adica asta e intrebarea:) )
Acest lucru se observa si in problema de mai sus pentru ca nodul 3 e nod critic.

Are cineva o sursa comentata fara stl? Am incercat sa implementez dar gresesc la stergere.  :fool:
edit: nu am reusit sa termin deoarece greser\sc stergerile. Din lene am renuntat sa rezolv pb asta fara stl.

Mai simplu posteaza, sau trimite sursa ta si noi corectam :)

A implementat cineva algoritmul lui Fleury? Nu prea stiu cum sa determin daca o muchie e punte(sau critica...) dupa update in mod eficient.
L.E.: Niciun test nu contine un graf care nu este conex?

"Pentru determinarea lantului, vom adaugata fictiv o muchie intre aceste doua noduri, dupa care vom aplica algoritmul de determinare a unui ciclu Eulerian. Eventual, acest ciclu determinat va fi 'rupt' in locul in care apare muchia adaugata si tiparit in ordinea corecta."

Eu am implementat algoritmul recursiv si totul merge perfect. Nu mai trebuie sa adaugi nicio muchie fictiva. Trebuie doar sa apelezi euler(nod de grad impar). Si merge. NU inteleg de ce ati scris chestia asta cu muchia. Va rog raspundeti-mi ca sa nu mor prost.

[email protected]

Chestia asta cu muchia a fost scrisa ca sa-ti arate intr-un mod elegant ca e practic aceeasi problema cu cea a ciclului eulerian.
Cuvantul 'fictiv' ar fi trebuit sa-ti dea un hint in sensul asta. Adopta un ton mai calm si mai cooperant, te rog.

Solutia prezentata ca fiind optima e O(M*N), eliminarea unei muchii se face in O(N) deci nu intra in timp pe niste teste bune.

De ce zici ca eliminarea unei muchii se face in O(N)?

Mi se pare destul de O(n)  :). Un varf poate sa aiba N vecini si ala pe care il stergi sa fie ultimul in lista.

Testele sunt slabe si nu diferentiaza o astfel de solutie de una optima.

Nu sunt testele slabe. Presupunand ca muchiile sunt distribuite relativ uniform, pe testele maxime marimea listelor de adiacenta e mult mai mica decat n.  Ai nevoie de un graf cu densitate mult mai mare ca sa busesti stergerea aia, ori e cam imposibil sa dai ca input un graf dens cu 100 000 de noduri.

Stergerea o poti face mai bine. Stergi muchia doar din v si o marchezi pentru eliminare intr-un vector. Astfel o vei sterge din lista lui w de-abia cand treci pe-acolo si o intalnesti, nefiind nevoie sa o mai cauti pe loc.

Deci e O(n + m).

Ce te face sa presupui ca muchiile sunt distribuite uniform? Vorbim de analiza in cazul cel mai defavorabil nu in cazul mediu. Considera graful urmator: N noduri (N par) 1 si 2 noduri speciale 1 are muchie catre toate cele N-2 noduri ramase, 2 la fel (in total 2*(N-2) muchii deci graf deloc dens) cati vecini are 1 si cat dureaza sa elimini un element din lista lui de vecini?

Poti sa tii un hash in care sa bagi muchiile sterse => stergere muchie O(1). Si probabil ca mai sunt si alte solutii. Dar nu pe stergerea muchiei se pune accentul la problema aceasta. E arhiva educationala, deci nu e nevoie de teste super puternice.

Stiu ca se poate, si cum se poate. Problema e ca fiind arhiva educationala omu vine si invata problema se uita si peste sursa oficiala, face stergerea in O(N) ia 100 la problema si zice "da dom'le stiu sa rezolv problema". Apoi se duce la concurs implementeaza aceeasi solutie si ia 50 de puncte pe teste mai bune si se intreaba "de ce?". Asta e singurul lucru pe care vroiam sa-l punctez.

Pana la urma cum e, trebuie ca toate nodurile sa aibe gradul par, sau pot exista fix 2 care au gradul impar :
A connected undirected graph is Eulerian if and only if every graph vertex has an even degree, or exactly two vertices have an odd degree.
Vad ca cele afirmatii se bat cap in cap ....

Toate nodurile au grad par <=> exista ciclu eulerian
Toate nodurile au grad par cu exceptia a fix 2 <=> exista lant eulerian

pentru prima figura (patratul cu doua diagonale ) care este solutia prin care nu treci de 2 ori printr-o latura si nu ridici creionul de pe foaie? ???

Nu exista nici o solutie. Tocmai pentru ca graful respectiv nu e eulerian.

Graful e orientat sau neorientat?

Eu am rezolvat-o presupunand ca e neorientat.

Da, se vede ca e neorientat din exemplu. Ar trebui specificat.

LE: Se pot mari restrictiile problemei un pic sa nu fie nevoie sa faci parsare si alte lucruri de genul asta?

Sursa oficiala ia 60 de puncte cu TLE pe ultimul test. Cred ca ar trebui marita putin limita de timp (pentru 100 de puncte trebuie parsata citirea).

Fixed.

Nu pot sa inteleg de ce evaluatorul imi spune "Fisier de iesire corupt", numele la fisier este corect si la urma inchid fisierul , pls help  ](*,)

Mie,pe testul de mai jos,algoritmul imi afiseaza 1 4 3 3 2 3 4 2 3 2 5 6 . Nu vad greseala din parcurgerea asta,insa evaluatorul imi da 0 puncte pe acest test (testul este din atasamentele evaluatorului). Ma poate lamuri cineva,va rog?  :D
6 12
2 5
2 3
3 3
4 3
6 1
3 2
1 4
3 2
5 6
2 4
4 3
3 2

A implementat cineva algoritmul lui Fleury?

Salutare, s-au schimbat cumva testele de la problema, aveam un algoritm pe care luam 100, acuma iau doar 80 pe el si in rest TLE
 :? :-'

O solutie care pentru testul
2 2
1 2
1 2
afiseaza 1 2 1 (ultimul 1 nu ar trebui sa apara conform enuntului) ia 100 de puncte.