Топологическая сортировка

Топологическая сортировка – размещение вершин в таком порядке, чтобы все дуги были направлены справа налево.

Рисунок 21. Пример топологической сортировки

Для того, чтобы провести топологическую сортировку графа, используется слегка модифицированный поиск в глубину:

#include<stdio.h>

int MAXN = 100;//Максимальное число вершин
int MAXM = 100;//Максимальное число ребер
int n;//Число вершин
int m;//Число ребер
int first;//Начальная вершина
int ans[MAXN];//Массив с отсортированными вершинами
int anscount = 0;//Количество вершин в отсортированном массиве

int b[MAXM];//b[i] - куда ведет ребро i
int bc;//количество ребер
int last[MAXN];//Последнее ребро, исходящее из вершины
int prev[MAXM];
/*prev[i] - предыдущее ребро, исходящее из той же вершины, что и ребро i.*/

void dfs(int p)
{//Передаем вершину    
    int i = last[p];
    //Начинаем перебирать ребра, начиная с последнего, исходящего из p
    while (i != -1)
{//Пока не дошли до последнего ребра
        dfs(b[i]);
        //Запускаем рекурсию в вершину, в которое ведет ребро i

        i = prev[i];
        //Переходим к предыдущему ребру.
    }

    /*После того, как мы запустили рекурсию во все вершины, в которые ведут ребра из p, мы записываем p в массив ответа*/
    ans[anscount++] = p;
}

int main()
{
    scanf(“%d%d”, &n, &m,);
    //Читаем количество вершин и ребер

    for (int i = 0; i < n; i++)
        last[i] = -1;
    /*Устанавливаем значения минимальных путей и отсутствие ребер из каждой вершину.*/

    //Читаем список ребер:
    for (int i = 0; i < m; i++)
{
        int l, r;
        scanf(“%d%d”, &l, &r);
        //Читаем начальную и конечную вершины i-го ребра
        
        bc++;
        b[bc] = r;
        //заносим вершину назначения данного ребра в массив
        prev[bc] = last[x];
        //Устанвливаем предыдущее ребро, как последнее, исходящее из x

        last[x] = bc;
        //Теперь последнее ребро – то, которое мы только что добавили.
    }

    dfs(first);
    //Запускаем dfs из первой вершины
    /*Сейчас в массиве ans будут все вершины в таком порядке, что ребра будут идти справа налево.*/
}