Topological Sort (Kahn's / DFS)

Key Signals & Indicators

• DAG dependency resolution problems (e.g. course scheduling)
• Finding topological ordering or verifying cycle existence
• Process ordering tasks under precedence constraints

// C++ Kahn's Algorithm (BFS Topological Sort) Template
#include <vector>
#include <queue>

std::vector<int> topologicalSort(int n, const std::vector<std::vector<int>>& adjList) {
    std::vector<int> inDegree(n, 0);
    for (int u = 0; u < n; ++u) {
        for (int v : adjList[u]) inDegree[v]++;
    }
    
    std::queue<int> q;
    for (int i = 0; i < n; ++i) {
        if (inDegree[i] == 0) q.push(i);
    }
    
    std::vector<int> order;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        order.push_back(u);
        
        for (int v : adjList[u]) {
            inDegree[v]--;
            if (inDegree[v] == 0) q.push(v);
        }
    }
    
    return order.size() == n ? order : std::vector<int>{}; // Empty if cycle detected
}