Здравствуйте, камрады😎 Сегодня у нас на разборе топологическая сортировка. Алгос, который может быть полезен при решении задач на графы. Идея Если коротко: у нас есть ориентированный граф, и нам нужен такой порядок вершин, чтобы все рёбра шли из более ранней вершины в более позднюю. Другими словами, чтобы никакая задача не “опережала” свою зависимость. Особенности Граф с циклом не сортируется Как ни расставляй вершины массива, по ребрам цикла невозможно идти строго “вправо”. Ациклический граф всегда можно отсортировать В нём всегда есть вершина без исходящих рёбер — её можно поставить последней. Убираем такие вершины по одной, пока граф не пуст — получаем массив, который потом разворачиваем. Реализация Реализация проще через DFS: Выходим из вершины, у которой нет новых исходящих рёбер; Продолжаем из тех вершин, исходящие ребра которых ведут только в уже посещённые вершины. Записываем вершины в порядке выхода из DFS и разворачиваем массив — получаем корректную топологическую сортировку. const int maxn = 1e5; bool used[maxn]; vector<int> t; void dfs(int v) { used[v] = true; for (int u : g[v]) if (!used[u]) dfs(u); t.push_back(v); } void topological_sort() { for (int v = 0; v < n; v++) if (!used[v]) dfs(v); reverse(t.begin(), t.end()); } Применение Топологическую сортировку можно использовать для проверки достижимости Если вершина a идёт позже вершины b в массиве — значит, из a до b достичь нельзя. Однако обратное не гарантируется — a может быть достижима из b или нет. Задачки Course Schedule Course Schedule II Longest Increasing Path in a Matrix Sort Items by Groups Respecting Dependencies Maximum Employees To Be Invited To A Meeting Ещё больше разборов и подборок задач на нашей 3х месячной олимпиадной смене по информатике @postupashki_prog