004 Sortare topologica

[•DITzoneC]

Aici puteti discuta despre problema Sortare Topologica.

[•anna_bozianu]

Am o nelamurire legata de evaluare. Prin sortarea topologica solutia nu este unica. Orice solutie corecta este punctata? Intreb pentru ca eu realizez lista sucesorilor si la parcurgerea listei sucesorii unui nod dat imi vin in ordine inversa fata de cum au aparut arcele la citire. Este posibil ca astfel solutia mea sa fie corecta dat alta decat cea din fisirerul OK al evaluatorului. Scuze daca gresesc cu ceva.

[•wefgef]

Orice solutie este acceptata .

[•anna_bozianu]

10x. Am rezolvat. Aveam eu o greseala.

[•sigrid]

Daca exista noduri izolate, ele pot fi afisate oriunde  ?

[•wefgef]

Da .

[•sigrid]

Multumesc pentru raspuns 

Apropo s-a refacut karma ta   ?

[•wefgef]

Cat de cat.. aveam 232 in momentul atacului terorist

[•sigrid]

Uite ca acum s-a refacut 

[•alexandru92]

imi zice si mie cineva unde pisici  gresesc    ........de 1h tot nu gasesc o solutie  :
http://infoarena.ro/job_detail/278562?action=view-source 
Am incercat o multitudine de solutii ............dar nici una nu-mi merge 

[•Florian]

Vezi ca trebuie sa citesti M muchii. Tu citesti doar N muchii. 

[•alexandru92]

multumesc    ....ar trebuii sa fiu mai atent ..........

[•xtreme]

O idee de rezolvare este sa introducem, pe rand, intr-o lista, nodurile care la un moment dat un gradul exterior zero. Odata ce un nod este introdus in lista, vom scoate nodul respectiv din graf si vom considera in continuare graful ramas. O implementare directa are complexitatea O(N2) si se gaseste aici. Daca rafinam aceasta idee, introducand succesiv nodurile intr-o coada, putem obtine complexitatea O(N+M), sursa se gaseste aici.

Aici cred ca vrea sa zica gradul interior in loc de gradul exterior.Gresesc?

[•alexandru92]

Aici cred ca vrea sa zica gradul interior in loc de gradul exterior.Gresesc?

Nu, nu gresesti

[•xtreme]

Aici cred ca vrea sa zica gradul interior in loc de gradul exterior.Gresesc?

Nu, nu gresesti

Nu e adevarat.Am studiat mai atent si m-am lamurit, gresisem...

[•alexandru92]

Nu e adevarat.Am studiat mai atent si m-am lamurit, gresisem...

,  da se pare ca sursa de la care m-am informat era gresita ... erau defintile fix invers  

[•S7012MY]

La probleme ar putea fi adaugata si problema honest de pe campion

[•chibicitiberiu]

E de-a dreptul ciudata problema asta.

Am facut rezolvarea cu DFS;
Solutia care imi da exact ca in exemplu ia 0 puncte.
Solutia care da total diferit de exemplu ia 100 puncte.

Diferenta e doar felul in care retin ordinea...

Pentru exemplu, imi da:

Cod:

 1 3 5 9 4 8 7 6 2 

[•skull]

Solutia nu este unica, iar rezultatul care-ti da tie pe exemplu este bun.

[•addy01]

Exista cineva care a facut problema asta cu algoritmul de sortare topologica nu cu DFS ?   si app...dc exista emoticonul asta ? 

[•wefgef]

si app...dc exista emoticonul asta ? 

http://www.urbandictionary.com/define.php?term=beating%20a%20dead%20horse

[•vladradu2014]

Am o mica problema. Primesc sig6(sigabrt) la primul test, in rest e ok. Nu stiu exact unde e problema, aloc suficienta memorie de fiecare data. Imi puteti da indicii?

[•freak93]

Signal 6 iei atunci cand imparti la 0 sau atunci cand folosesti functii din STL gresit (cum ar fi find, lower_bound pe 2 iteratori care nu sunt din aceeasi structura, sau care nu pastreaza ordinea). Pentru  probleme de memorie primesti deobicei Signal 11

[•Consti.001]

Am o mare intrebare??? De ce trebuie bagat in lista elemtul la finalul functiei DFS si nu la inceputul ei??? Daca o pun la inceput imi da fix exemplul dar iau 0 puncte.

[•jordan1998]

cred ca trebuie sa fie grad interior,nu?
adica :
// deg

• = gradul exterior al nodului x

si dupa daca gaseste perechea x y face deg[y]++