infoarena

Aici puteti discuta despre problema Sortare Topologica (http://infoarena.ro/problema/sortaret).

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.

Orice solutie este acceptata :).

10x. Am rezolvat. Aveam eu o greseala.

Daca exista noduri izolate, ele pot fi afisate oriunde  :) ?

Da :).

Multumesc pentru raspuns  :)

Apropo s-a refacut karma ta   :rastabanana: ?

Cat de cat.. aveam 232 in momentul atacului terorist :P

Uite ca acum s-a refacut  :P

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  :'(

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

multumesc    :rotfl: ....ar trebuii sa fiu mai atent :D ..........

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?

Nu, nu gresesti :D

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

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

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

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:

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

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

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

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?

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

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.

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

https://pastebin.com/9deg6jSi se poate uita cineva si sa imi spuna de ce gresesc sau sa imi dea un test care nu merge? :-k
 

Buna!
Mi-ar putea spune cineva care e problema cu sursa de pe link?

http://www.infoarena.ro/job_detail/2000091?action=view-source

Evaluatorul scrie la fiecare executie ca sunt "Prea putine noduri afisate", dar am descarcat atasamentele si testandu-le, fisierele de iesire au continut exact N numere de fiecare data. Si si rezultatul mi se pare corect.
Ajutor pls  :'(

Nevermind