034 Ciclu Eulerian

[•pauldb]

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

[•APOCALYPTO]

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.

[•S7012MY]

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

[•BitOne]

Are cineva o sursa comentata fara stl? Am incercat sa implementez dar gresesc la stergere. 

Mai simplu posteaza, sau trimite sursa ta si noi corectam

[•MciprianM]

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?

[•livium]

"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]

[•klamathix]

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.

[•invatacel]

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.

[•klamathix]

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

[•invatacel]

Cod:

void sterge( int v, int w ) 
{
  deg[v]--, deg[w]--;
  G[v].pop_front();
  TR( G[w], it )
   if( *it == v ) 
   {
       G[w].erase( it );
       break;
   }
}

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.

[•invatacel]

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

[•klamathix]

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

[•invatacel]

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?

[•Florian]

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.

[•invatacel]

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.

[•ucc_5]

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

[•toni2007]

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

[•adelinac]

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?

[•pauldb]

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

[•Bit_Master]

Graful e orientat sau neorientat?

[•S7012MY]

Eu am rezolvat-o presupunand ca e neorientat.

[•Bit_Master]

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?

[•SebiSebi]

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

[•klamathix]

Fixed.

[•ctlin04]

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