Topological sorting

Order tasks so every prerequisite comes before the task that depends on it. This works on directed acyclic graphs (DAGs).

Prerequisites: Basic C++ input/output, vectors, loops, and the preceding graph lessons.

Build the idea

1. Count each vertex’s incoming edges.
2. Put every zero-indegree vertex into a queue.
3. Remove a vertex, append it to the order, and decrement its neighbors’ indegrees.
4. If fewer than n vertices were removed, the graph contains a directed cycle.
5. in[v] counts remaining prerequisites. A cycle leaves vertices with positive indegree, so the processed count is smaller than n.

This is a complete program. Compile with C++17 and enter the input described below.

// Key idea: in[v] counts remaining prerequisites. A cycle leaves vertices with positive indegree, so
// the processed count is smaller than n.
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<algorithm>
#include<functional>
#include<numeric>
#include<utility>
using namespace std;
vector<int>topo(const vector<vector<int>>&g){
    int n=(int)g.size()-1;
    vector<int>in(n+1),order;
    for(int v=1;v<=n;++v){
        for(int u:g[v]){
            ++in[u];
        }
    }
    queue<int>q;
    for(int v=1;v<=n;++v){
        if(!in[v]){
            q.push(v);
        }
    }
    while(!q.empty()){
        int v=q.front();
        q.pop();
        order.push_back(v);
        for(int u:g[v]){
            if(--in[u]==0){
                q.push(u);
            }
        }
    }
    if((int)order.size()!=n){
        return {};
    }
    return order;
}
template<class T>void printValues(const vector<T>&values){
    for(int i=0;i<(int)values.size();i++){
        if(i>0){
            cout<<' ';
        }
        cout<<values[i];
    }
    cout<<'\n';
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    vector<vector<int>>graph(n+1);
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        graph[a].push_back(b);
    }
    vector<int>order=topo(graph);
    if(order.empty()){
        cout<<"CYCLE\n";
    }
    else{
        printValues(order);
    }
}

Complexity analysis

O(V + E) time, O(V) auxiliary space.

Example input and output

Read n m and m directed edges a b, meaning a must precede b (n≥1). Print a topological order, or CYCLE. Several valid orders may exist.

Input

4 3
1 2
1 3
3 4

Output

1 2 3 4

Only vertex 1 initially has indegree zero. Removing it makes 2 and 3 available, and processing 3 releases 4.

Practical applications

Use topological order for prerequisite scheduling and dynamic programming on DAGs.

Check your understanding

When does a topological order exist?

Put it into practice

Output a valid order for courses with prerequisites, or report a cycle.