Задание состоит из двух частей, первая из которых обязательны для выполнения, вторая выполняется для получения оценки «отлично».
Бинарным отношением на множестве 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
.
То же задание, но граф хранить в виде списка смежности (для каждой вершины хранится список вершин, в которые есть ребро из данной вершины).