Zadanie 1

Napisać w asemblerze NASM program sortujący topologicznie acykliczny graf skierowany (DAG). Algorytm można znaleźć np. w książce [1].

Program wczytuje opis grafu ze standardowego wejścia. Dane wejściowe to ciąg liczb oddzielonych białymi znakami (spacja, tabulacja, koniec wiersza). Pierwsza liczba to ilość wierzchołków grafu N. Wierzchołki numerowane są od 0 do N-1. Następnie dane wejściowe zawierają N ciągów liczb opisujących sąsiadów kolejnych wierzchołków. Każdy taki ciąg zaczyna się od liczby sąsiadów s_i wierzchołka i, a potem zawiera s_i numerów kolejnych sąsiadów. Zakładamy, że dane wejściowe opisują poprawny DAG.

Program wypisuje wynik na standardowe wyjście. Wynik to ciąg numerów wierzchołków w porządku topologicznym oddzielonych spacjami.

Program powinien obsługiwać grafy zawierające do 8192 wierzchołków. Nie wolno korzystać z żadnych bibliotek. Dopuszczalne jest statyczne zaalokowanie pamięci potrzebnej na maksymalny możliwy graf, ale używać należy tylko takiego jej spójnego kawałka, jaki jest niezbędny do przetworzenia aktualnego grafu. Pozostawienie wewnątrz tego spójnego kawałka niewielkich nieużywanych fragmentów jest dopuszczalne, jeśli ze względów efektywnościowych korzystne jest wyrównywanie pewnych adresów.

Program będzie oceniany w skali od 0 do 5 punktów. Przy ocenie będą brane pod uwagę następujące kryteria:

• Czy program działa poprawnie dla poprawnych danych wejściowych?
• Czy program nie narusza ochrony pamięci?
• Jaka jest wewnętrzna reprezentacja grafu?
• Czy kodowanie jest zwięzłe?
• Czy program działa dostatecznie szybko?
• Czy program jest w sensowny sposób podzielony na procedury?
• Czy program zawiera komentarze? Dla każdej procedury należy zamieścić krótki opis jej działania, opis argumentów wejściowych i wyjściowych, listę modyfikowanych rejestrów i opis efektów ubocznych (jeśli są).

[1] T. H. Cormen, Ch. E. Leiserson, R. L. Rivest, Wprowadzenie do algorytmów.