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

Материал из Олимпиадное программирование в УлГТУ
Версия от 15:16, 24 мая 2023; Ctrlalt (обсуждение | вклад)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

TLDR

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

  • Порядок топологической сортировки — порядок убывания времени выхода из вершины.
  • Каждую вершину при выходе из DFS кладём в контейнер, который после переворачиваем (также можно использовать стек).
  • Время работы O(V + E).
void dfs(vector<vector<int>> &graph, int v, vector<int> &visited, vector<int> &order) {
    visited[v] = 1;
    for (int to : graph[v])
        if (!visited[to])
            dfs(graph, to, visited, order);
    order.push_back(v);
}

for (int v = 0; v < graph.size(); v++)
    if (!visited[v])
        dfs(graph, v, visited, order);
reverse(order.begin(), order.end());

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

  • Пока в графе остались вершины, находим любой исток, добавляем его к ответу и удаляем из графа вместе со всеми исходящими рёбрами.
  • Данный алгоритм, в отличие от предыдущего, позволяет найти лексикографически минимальную топологическую сортировку.
  • Время работы O(VlogV + E).
vector<int> inDegree(graph.size());
for (int v = 0; v < graph.size(); v++)
    for (int to : graph[v])
        inDegree[to]++;

set<pair<int, int>> q;
for (int v = 0; v < graph.size(); v++)
    q.insert({ inDegree[v], v });

vector<int> order;
while (!q.empty()) {
    int v = q.begin()->second;
    q.erase(q.begin());

    order.push_back(v);

    for (int to : graph[v]) {
        q.erase({ inDegree[to], to });
        inDegree[to]--;
        q.insert({ inDegree[to], to });
    }
}

Ссылки

Теория:

Демонстрация:

Код:

Задачи: