Задание для групп БЛК-151/152 бакалавриата ВШЭ по курсу теории алгоритмов
Программа выполняет топологическую сортировку ориентированного графа, заданного списком рёбер в поданном на вход файле (или прочитанного из stdin).
Программа должна повторять поведение утилиты tsort из состава GNU Coreutils, описанное в документации:
https://www.gnu.org/software/coreutils/manual/html_node/tsort-invocation.html
N.B.: у графа может быть несколько топологических сортировок, какую из них выберет ваша реализация — не принципиально.
Рекомендуется установка в виртуальное окружение. Режим editable (флаг -e) позволяет обновлять программу без дополнительной переустановки:
$ git clone git@github.com:<username>/pytsort.git
$ cd pytsort
$ python3 -m venv .env
$ . .env/bin/activate
$ pip install -e .
$ pytsort --version
pytsort @ HSE Algorithms S18
pytsort ожидает на вход список ориентированных рёбер графа, заданый парами вершин, разделённых любыми пробельными символами (в том числе и переносом строки).
В частности, следующий ввод:
pytsort <<EOF
a b c
d
e f
b c d e
EOF
интерпретируется как граф с рёбрами <a,b>, <c,d>, <e,f>, <b,c> и <d,e>. Вызов с нечётным количеством вершин должен приводить к ошибке.
Для проверки задания необходимо прислать pull-request (PR) в этот репозиторий. При успешной сдаче PR закрывается без мёржа, оценка будет сообщаться в комментариях.