Introduction

С возвращением в серию Алгоритмы на графах! На этот раз мы работаем с ориентированным графом, где каждое ребро имеет направление: ребро u -> v означает, что u должно идти перед v.

Топологическая сортировка выстраивает вершины ориентированного ациклического графа (DAG) в линию так, чтобы каждое ребро указывало вперед. Она отвечает на такие вопросы, как «в каком порядке я могу проходить курсы с учетом их предварительных условий?»

Граф задан как n (вершины от 0 до n - 1) и edges, плоский массив ориентированных пар [u0, v0, u1, v1, ...], где каждая пара означает u -> v.

Давайте начнем!