Given a directed graph with v vertices and e edges, you would like to sort the vertices in a particular order. If there is an edge that goes from v1 to v2, then the source vertex v1 should appear earlier in the array of vertices than v2. So, after sorting the vertices, each edge should take one from a vertex with a smaller index to a vertex with a larger one.
Notice that there can be different valid topological sorting orders.
On the other hand, if the graph contains cycles, there are no valid topological sorting orders.
The algorithm can be implemented with a DFS that starts from every vertex which hasn’t been visited so far. On each DFS iteration, we can first recursively add all the child nodes of the current vertex, and only after all the child vertices are processed, add the current one to the answer list. This will ensure that the source vertex appears later than all the ones reachable from it. By the end of the algorithm, we will reverse the order in the answer list:
used = [False] * n # used vertices
order =  # topological order
def dfs(v): # dfs
used[v] = True # mark vertex as used
for to in g[v]: # for each vertex to adjacent to v
if not used[to]: # if to is not used
dfs(to) # dfs from to
order.append(v) # add v to topological order
for i in range(n): # for each vertex
if not used[i]: # if vertex is not used
dfs(i) # dfs from vertex
print(*order[::-1]) # print topological order
Challenge: Organize the Course Schedule
You are given n courses that you’d like to take. There are p prerequisites in total. Each prerequisite represents a pair of courses meaning that you must take the course before you take course (if the pair is 1, 2 - it means that you need to take course 2 before taking course 1).
You need to check if it’s possible to finish all the courses.
The first line of the input contains two integers n and p (1 ≤ n, p ≤ 10 000).
The next p lines contain pairs of integers (1 ≤ ≤ n).
The program should print Yes if it’s possible to take all the courses and No otherwise.