Сегодня у нас на разборе топологическая сортировка. Алгос, который может быть полезен при решении задач на графы.
Идея
Если коротко: у нас есть ориентированный граф, и нам нужен такой порядок вершин, чтобы все рёбра шли из более ранней вершины в более позднюю.
Другими словами, чтобы никакая задача не “опережала” свою зависимость.
Особенности
Граф с циклом не сортируется
Как ни расставляй вершины массива, по ребрам цикла невозможно идти строго “вправо”.
Ациклический граф всегда можно отсортировать
В нём всегда есть вершина без исходящих рёбер — её можно поставить последней.
Убираем такие вершины по одной, пока граф не пуст — получаем массив, который потом разворачиваем.
Реализация
Реализация проще через 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