Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | sortaret.in, sortaret.out | Sursă | ad-hoc |
| Autor | Arhiva Educationala | Adăugată de |  Tabara Mihai •Tabara |
| Timp execuţie pe test | 0.125 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Poti vedea testele pentru aceasta problema accesand atasamentele.Vezi solutiile trimise | Statistici
Sortare topologica
Enuntul problemei de sortare topologica este urmatorul: fie o lista de n obiecte, si o lista de preferinte. O preferinta este exprimata in felul urmator: obiectul a este preferat obiectului b. Se cere sa se ordoneze cele n obiecte, in ordinea descrescatoare a preferintelor, conform preferintelor exprimate in lista de preferinte. O reprezentare convenabila a spatiului acestei probleme presupune construirea unui graf care sa aiba in varfurile sale cele n obiecte. Vom trasa un arc in graf, de la varful i la varful j daca obiectul asociat varfului j este preferat obiectului asociat varfului i. Astfel, un obiect care este cel mai preferat in lista de obiecte va avea asociat un nod in graf care nu are succesori, adica in care doar intra arcuri. Pe scurt, o sortare topologica a varfurilor unui graf orientat aciclic este o operatie de ordonare liniara a varfurilor, astfel incat, daca exista un arc (i, j), atunci i apare inaintea lui j in aceasta ordonare.
Date de intrare
Fisierul de intrare sortaret.in ...
Date de iesire
In fisierul de iesire sortaret.out ...
Restrictii
- ... ≤ ... ≤ ...
Exemplu
| sortaret.in | sortaret.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicatie
...
