Topological Sorting
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 orderChallenge: 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 You need to check if it’s possible to finish all the courses.
Input
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 Output
The program should print
Yes if it’s possible to take all the courses and No otherwise.Examples
Input | Output |
2 1
2 1 | Yes |
2 2
2 1
1 2 | No |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB