Kahn’s Algorithm and Cycle Detection in Directed Graphs

Kahn's algorithm is quite simple and intuitive. We just calculate the indegree of each node in the graph and start with those that have an indegree of 0 (by pushing them into the queue). Next, we take the nodes out of the queue one by one, iterate over their neighbors, and simulate edge removal by simply decreasing the indegree of each neighbor by 1. If during that process the indegree of any neighbor becomes 0, we push that node into the queue.

A simple analogy is the process of removing bricks from a pile — start from the top and keep removing those that have no one above them, and continue until the pile is empty.

This awesome creature named Kahn's algorithm is not limited to just performing a topological sort. Along with that, it naturally detects a cycle for us (yes, a "2-in-1" product).

But before diving into the cycle detection part, let’s recall a few important properties of cycles in directed graphs:

1. Every node in a cycle must have at least one incoming edge from another node within that same cycle.

2. If every node in the cycle has an incoming edge, then there can’t be any node with 0 indegree inside the cycle.

3. Therefore, we can only approach the cycle from outside — never from inside.

Another important thing to keep in mind is that a node becomes part of the solution vector only through the queue (meaning, a node first goes into the queue and then becomes part of the solution).

So, every time we approach a node belonging to a cycle from outside, its indegree decreases by 1. But we only push a node into the queue when its indegree becomes 0. Can that happen for a node inside a cycle? The answer is simply no.

For every node inside a cycle (call it the destination node), there’s always an incoming edge from another node within that same cycle (call it the source node). We can only push this destination node into the queue if its source node somehow enters the queue first — because that’s the only way to remove the edge. But that’s impossible, since every node inside the cycle is waiting for its preceding node to go first.

This circular dependency ensures that none of the nodes in the cycle will ever be pushed into the queue, and hence, they’ll never appear in the topological sort.

Therefore, the number of nodes in the final topological order = total nodes − nodes belonging to cycles.

So if a cycle exists, the size of the topological order will always be smaller than the total number of nodes in the graph.

bool isCyclic(vector<vector<int>>& grid)  {

    size_t m = grid.size();

    vector<int> indegree(m, 0);

    for (size_t i = 0; i < m; i++) {

        for (size_t j = 0; j < grid[i].size(); j++) {
            ++indegree[grid[i][j]];
        }
    }

    queue<int> bfsq;

    for (size_t i = 0; i < m; i++) {

        if (indegree[i] == 0) {
            bfsq.push(i);
        }
    }

    vector<int> solution;

    while (!bfsq.empty()) {

        int node = bfsq.front();
        bfsq.pop();

        solution.push_back(node);

        size_t n = grid[node].size();

        for (size_t i = 0; i < n; i++) {

            int it = grid[node][i];

            if(--indegree[it] == 0) {
                bfsq.push(it);
            }
        }
    }

    return solution.size() < m;
}