Hello Codeforces!

What is Topological Sort?

Topological Sort is an algorithm used to arrange nodes in a linear sequence. If there is a condition that node $$$u$$$ must be completed before node $$$v$$$, then $$$u$$$ must appear first in the ordering.

To visualize it simply, think of it as a "prerequisite tree." For example, you cannot study a Data Structures (DS) course before you finish Introduction to Programming.

Time Complexity: $$$O(V + E)$$$

Implementation in Python

In Python, there is a handy built-in library called graphlib that does this sorting easily. All you have to do is pass it a Dictionary containing each subject and a List of the subjects that must be finished before it:

from graphlib import TopologicalSorter, CycleError

# Dictionary containing each subject and its prerequisites
preds = {
    1: [],     # Subject 1 has no prerequisites
    2: [1],    # Subject 2 requires subject 1 to be finished first
    3: [1, 2]  # Subject 3 requires subjects 1 and 2
}

ts = TopologicalSorter(preds)

try:
    order = list(ts.static_order())
    print("Study Order:", *order) # Study Order: 1 2 3
except CycleError:
    print("-1\n")

Happy coding!