Given a directed graph with
eedges, you would like to sort the vertices in a particular order. If there is an edge that goes from
v2, then the source vertex
v1should 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
ncourses that you’d like to take. There are
pprerequisites 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
p(1 ≤ n, p ≤ 10 000).
plines contain pairs of integers
(1 ≤ ≤ n).
The program should print
Yesif it’s possible to take all the courses and
2 1 2 1
2 2 2 1 1 2
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB