Topological Sort (Kahn's Algorithm)

Concept

Topological sort orders nodes of a DAG (Directed Acyclic Graph) so that for every edge u -> v, u comes before v. Kahn's algorithm uses BFS with in-degree counting: start from nodes with in-degree 0, remove them, decrease neighbors' in-degrees, and repeat.

When to Use

▸Course prerequisites — finding a valid order to take courses
▸Task scheduling with dependencies
▸Build systems (compile order)
▸Detecting if a directed graph has a cycle (if topo sort doesn't include all nodes, there's a cycle)

Intuition

Think of courses with prerequisites. Start with courses that have no prerequisites (in-degree 0) — you can take them right away. After completing them, some new courses become available (their prerequisites are now met). Take those next. Repeat until all courses are taken. If you get stuck with remaining courses that all have unmet prerequisites, there's a circular dependency (cycle).

Complexity

Time

O(V + E)

Space

O(V + E)

Template Code

cpp

#include<bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(0), cin.tie(0);

    int numCourses, m;
    cin >> numCourses >> m;

    vector<vector<int>> adj(numCourses);
    vector<int> inde(numCourses, 0);
    vector<int> order;

    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        adj[b].push_back(a);
        inde[a]++;
    }

    queue<int> q;
    for(int i = 0; i < numCourses; i++){
        if(inde[i] == 0) q.push(i);
    }

    while(!q.empty()){
        int u = q.front();
        q.pop();

        order.push_back(u);

        for(int &v : adj[u]){
            inde[v]--;
            if(inde[v] == 0) q.push(v);
        }
    }

    if(order.size() != numCourses){
        cout << "IMPOSSIBLE\n";
    }
    else{
        for(int &x : order){
            cout << x << " ";
        }
        cout << "\n";
    }

    return 0;
}

// Sample Input:
// 4 4
// 1 0
// 2 0
// 3 1
// 3 2
//
// Sample Output:
// 0 1 2 3