Топологическая сортировка: различия между версиями

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
Строка 9: Строка 9:
   
   
  void dfs(int v) {
  void dfs(int v) {
     visited[v] = 1;
     visited[v] = true;
     for (int to : graph[v])
     for (int to : graph[v])
         if (!visited[to])
         if (!visited[to])

Версия от 21:10, 7 апреля 2021

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

  • Порядок топологической сортировки — порядок убывания времени выхода из вершины.
  • Каждую вершину при выходе из DFS кладём в контейнер, который после переворачиваем (также можно использовать стек).
  • Время работы O(V + E).
vector<vector<int>> graph(vertexCount);
vector<bool> visited(vertexCount);
vector<int> order;

void dfs(int v) {
    visited[v] = true;
    for (int to : graph[v])
        if (!visited[to])
            dfs(to);
    order.push_back(v);
}

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

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

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

vector<int> inDegree(vertexCount);
for (int v = 0; v < vertexCount; v++)
    for (int to : graph[v])
        inDegree[to]++;

set<pair<int, int>> q;
for (int v = 0; v < vertexCount; 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 });
    }
}

Ссылки

Теория:

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

Код:

Задачи: