Algorithms and Data Structures

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 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.


2 1 2 1
2 2 2 1 1 2


Time limit: 1 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue