Задание состоит из двух частей, первая из которых обязательны для выполнения, вторая выполняется для получения оценки «отлично».
Бинарным отношением на множестве A будем называть подмножество
декартова произведения M x M, т.е. некоторое множество упорядоченных
пар, каждый элемент которых является элементом множества A.
Например, отношение > (больше) является бинарным отношением на множестве
{1, 2, 3, 4} и содержит пары
(2, 1), (3, 1), (4, 1), (3, 2), (4, 2), (4, 3).
Будем говорить, что истинно утверждение a R b, если пара
(a, b) принадлежит бинарному отношению R.
Пусть дано некоторое бинарное отношение R на конечном множестве A.
Задачей топологической сортировки является выстраивание элементов множества A
в последовательность a1, a2, ..., aN
так, что для любой пары (ai, aj) такой, что
истинно ai R aj, выполняется условие
i < j.
Если представить отношение в виде ориентированного графа (элементы множества являются вершинами,
ребро из вершины a в вершину b существует тогда и только тогда, когда истинно
a R b), то задача может быть сформулирована следующим образом:
перечислить вершины графа в таком порядке, чтобы для любого ребра графа его начальная вершина
была перечислена раньше конечной. На рисунке слева изображен исходный граф, справа его вершины
перечислены в требуемом порядке.
Можно привести следующий пример использования топологической сортировки: допустим, есть некоторое количество заданий, причем выполнение некоторых из них невозможно до тех пор, пока не будут выполнены какие-либо другие задания. Это множество заданий представляется в виде ориентированного графа, а в результате топологической сортировки вершин этого графа определяется последовательность выполнения заданий, удовлетворяющая всем условиям.
Ясно, что выполнить топологическую сортировку возможно не в любом графе, а только в таком, в котором отсутствуют циклы. Описанный ниже алгоритм выполняет топологическую сортировку графа без циклов.
Для ускорения работы алгоритма можно хранить в массиве количество ребер, входящих в данную вершину, и обновлять это количество при удалении каждого ребра.
Во входном файле input.txt вводится граф в виде списка ребер. Считать его в матрицу
смежности (двумерный массив, элемент (i, j) которого равен 1,
если в графе есть ребро из вершины i в вершину j, и 0
в противном случае) и выполнить топологическую сортировку этого графа. Результат
(последовательность вершин или сообщение о наличии цикла в графе) выдать в файл
output.txt.
То же задание, но граф хранить в виде списка смежности (для каждой вершины хранится список вершин, в которые есть ребро из данной вершины).