Wprowadzenie

Witaj ponownie w serii Algorytmy grafowe! Tym razem pracujemy z grafem skierowanym, w którym każda krawędź ma kierunek: krawędź u -> v oznacza, że u musi wystąpić przed v.

Sortowanie topologiczne układa wierzchołki skierowanego grafu acyklicznego (DAG) w kolejności liniowej tak, aby każda krawędź wskazywała do przodu. Odpowiada na pytania takie jak: „W jakiej kolejności mogę realizować kursy, biorąc pod uwagę ich wymagania wstępne?”

Graf jest podany jako n (wierzchołki od 0 do n - 1) oraz edges, płaska tablica skierowanych par [u0, v0, u1, v1, ...], w której każda para oznacza u -> v.

Zaczynajmy!