10305. Порядок задач

Джону необходимо выполнить n задач. К сожалению, задачи не являются независимыми друг от друга. Для выполнения одной задачи может потребоваться выполнение до этого некоторых других.

Вход. Состоит из нескольких тестов. Каждый тест начинается двумя целыми числами n (1 ≤ n ≤ 100) и m. Через n обозначено количество задач (пронумерованных от 1 до n), через m – количество отношений между задачами. В каждой из следующих m строк заданы два целых числа i и j, означающих, что задача i должна быть сделана до выполнения задачи j. Последняя строка содержит n = m = 0 и на обрабатывается.

Выход. Для каждого теста в отдельной строке вывести n чисел – один из возможных порядков выполнения задач.

Пример входа	Пример выхода
5 4 1 2 2 3 1 3 1 5 0 0	1 4 2 5 3

РЕШЕНИЕ

графы – топологическая сортировка

Анализ алгоритма

В задаче следует произвести топологическую сортировку вершин ориентированного графа. Это совершается при помощи обхода в глубину. Используется дополнительный массив top, в который заносятся вершины в порядке завершения их обработки процедурой поиска в глубину.

Реализация алгоритма

Матрица смежности графа хранится в массиве mas размера MAX.

#define MAX 101

int mas[MAX][MAX], used[MAX], top[MAX];

Функция поиска в глубину, совершающая топологическую сортировку.

void dfs(int i)

{

int j;

used[i] = 1;

for(j = 1; j <= n; j++)

if (mas[i][j] && !used[j]) dfs(j);

top[++ptr] = i;

}

Основная часть программы. Читаем входной граф.

while(scanf("%d %d",&n,&m),n + m > 0)

{

memset(mas,0,sizeof(mas));

memset(used,0,sizeof(used));

ptr = 0;

for(i = 0; i < m; i++)

{

scanf("%d %d",&a, &b);

mas[a][b] = 1;

}

Запускаем обход в глубину.

for(i = 1; i <= n; i++)

if (!used[i]) dfs(i);

Выводим вершины графа в топологически отсортированном порядке.

for(i = n; i >= 1; i--)

printf("%d ",top[i]);

printf("\n");

}