---
tags: Graph Theory
title: Topological Sort
---

# 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());
}