Problem Description

Given a DAG (directed acyclic graph), find out a sequence

$\{a_1,\dots ,a_n\}$
such that if

$i<j$, you need to go through

$a_i$ before you go to

$a_j$.

Kahn's Algorithm

vector<vector<int>> adj;

vector<int> topological_sort() {
    int n = adj.size();
    
    vector<int> indeg(n, 0);
    for (int u = 0; u < n; ++u) {
        for (int v : adj[u])
            ++indeg[v];
    }
    
    queue<int> q;
    for (int i = 0; i < n; ++i)
        if (indeg[i] == 0) 
            q.push(i);
    
    vector<bool> vis(n, false);
    vector<int> topoSort;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = true;
        
        topoSort.push_back(u);
        for (int v : adj[u]) {
            --indeg[v];
            if (!vis[v] && indeg[v] == 0) 
                q.push(v);
        }
    }
    return topoSort; // if topoSort.size() < n, then there's cycle on the graph
}

Depth First Search

Besure that the graph is a DAG before using this algorithm.

vector<vector<int>> adj;
vector<int> timeStamp;
vector<bool> vis;

void dfs(int u) {
    vis[u] = true;
    for (int v : adj[u]) 
        if (!vis[v]) 
            dfs(v);
    
    timeStamp.push_back(u);
}

void topological_sort() {
    int n = adj.size();
    for (int i = 0; i < n; ++i)
        if (!vis[i])
            dfs(i);
            
    reverse(timeStamp.begin(), timeStamp.end());
}