In-Depth Analysis of Topological Sorting: Kahn's Algorithm and Its Optimization

Core Logic and Mathematical Principles

Topological sorting is an algorithm that provides a linear ordering of the vertices in a Directed Acyclic Graph (DAG). After sorting, for any directed edge $(u, v)$ in the graph, vertex $u$ must appear before vertex $v$ in the sorted order.

In the NOIP framework, the core algebraic principles and state control of topological sorting consist of the following three key elements:

1. In-Degree Driven Paradigm: Kahn's Algorithm (Modified BFS)

The essence of Kahn's algorithm is dynamic topological convergence based on the elimination of zero in-degree nodes.

Physical Meaning: The in-degree of a vertex represents the number of prerequisite conditions that must be satisfied for the task. A node with an in-degree of $0$ means it has no prerequisites and can be executed immediately.
Dynamic Process: The algorithm maintains a set of zero in-degree states (queue). Each time, it extracts a vertex $u$ from the set and adds it to the topological sequence, while logically deleting all outgoing edges $(u, v)$ from $u$. This causes the in-degree of its subsequent adjacent node $v$ to decrease by 1 ($ ext{in ext{_}degree}[v] ightarrow ext{in ext{_}degree}[v] - 1$). If $v$'s in-degree becomes $0$, it indicates that all prerequisites are satisfied, and it seamlessly joins the zero in-degree set.
Time Complexity: Each vertex is enqueued once, and each edge is scanned once, resulting in a strict complexity of $O(V + E)$.

2. Topological Criterion for Cycle Detection

If there exists a directed cycle in the graph (e.g., $A o B o C o A$), the in-degrees of all nodes within the cycle will never reach $0$ after the external relaxation is exhausted. Therefore, they can never enter the zero in-degree queue.

No-Solution Topological Criterion: When the queue is empty and the algorithm terminates, if the number of vertices in the final topological sequence is strictly less than the total number of vertices $N$ ($ ext{cnt} < N$), it mathematically indicates that the graph contains a directed cycle and cannot complete topological sorting.

3. Selection of the Globally Lexicographically Smallest Topological Chain

In many competitive scenarios, the positions satisfying the topological relationships are often not unique. If the problem explicitly requires outputting the globally lexicographically smallest topological sequence, the traditional FIFO queue (std::queue) will not suffice.

Optimization Principle: It is necessary to seamlessly switch the data structure of the zero in-degree set to a min-heap (priority queue, std::priority_queue). Each time multiple nodes satisfy an in-degree of $0$, the heap structure ensures that the node with the smallest identifier is dequeued first, thus greedily constructing a globally lexicographically smallest valid topological chain.

Algorithm Derivation and State Design

1. State Design of Kahn's Algorithm

Define a one-dimensional counting array in_degree[i], and synchronize the execution when reading the edge $(u, v)$: in_degree[v]++.

Initialization: Scan the entire graph and push all nodes satisfying in_degree[i] == 0 into the priority queue.
State Transition Equation: For the current dequeued zero in-degree node $u$, iterate through the outgoing edges in its adjacency list. For each endpoint $v$:

$$ ext{in ext{_}degree}[v] ightarrow ext{in ext{_}degree}[v] - 1$$

$$ ext{if } ( ext{in ext{_}degree}[v] == 0) ext{ pq.push}(v)$$

C++ Standard Source Code (Template for Globally Lexicographically Smallest Topological Sorting)

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

const int MAXN = 100005;

std::vector<int> adj[MAXN]; // Adjacency list for directed graph
int in_degree[MAXN];       // Record in-degree of each node
std::vector<int> topo_res;  // Store the final generated topological sequence

bool topological_sort(int n) {
    // Core strategy: use min-heap to ensure the smallest numbered node among all nodes with in-degree 0 is dequeued first
    std::priority_queue<int, std::vector<int>, std::greater<int>> pq;

    // 1. Global scan, merge initial in-degree 0 points into the state heap
    for (int i = 1; i <= n; ++i) {
        if (in_degree[i] == 0) {
            pq.push(i);
        }
    }

    // 2. Topological iteration expansion
    while (!pq.empty()) {
        int u = pq.top();
        pq.pop();
        topo_res.push_back(u); // Merge into final topological sequence

        // Iterate through all outgoing edges from u
        for (size_t i = 0; i < adj[u].size(); ++i) {
            int v = adj[u][i];
            in_degree[v]--; // Logically cut the edge $(u, v)$, decrease the in-degree of endpoint by 1

            // Must strictly determine at the moment of == 0
            if (in_degree[v] == 0) {
                pq.push(v);
            }
        }
    }

    // 3. Algebraic check for cycle detection
    // If the number of points in the final generated sequence is not equal to the total number of points, it indicates that there is a cycle in the directed graph, and the topological chain is broken
    return topo_res.size() == static_cast<size_t>(n);
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n, m;
    if (!(std::cin >> n >> m)) return 0;

    for (int i = 0; i < m; ++i) {
        int u, v;
        std::cin >> u >> v;
        adj[u].push_back(v); // Establish directed edge u -> v
        in_degree[v]++;      // Add in-degree for endpoint v
    }

    if (!topological_sort(n)) {
        std::cout << -1 << "\n"; // The graph contains a directed cycle, topological sorting failed
    } else {
        for (int i = 0; i < n; ++i) {
            std::cout << topo_res[i] << (i == n - 1 ? "" : " ");
        }
        std::cout << "\n";
    }

    return 0;
}

NOIP Practical Pitfall Guide

Confusing "Globally Lexicographically Smallest Topological Order" with "Reverse Topological Order": This is a classic pitfall in competitive programming problems. Some problems require that nodes with smaller identifiers be as forward as possible, which can easily lead one to think that simply using a min-heap with Kahn's algorithm suffices. However, "globally lexicographically smallest" and "making smaller identifiers as forward as possible" are not mathematically equivalent (for example: the sequence $[1, 4, 2, 3]$ is lexicographically smaller than $[2, 1, 3, 4]$, but the latter has 1 appearing earlier).

Tactical Correction: If the problem requires making smaller nodes as forward as possible, the correct approach is to build a reverse graph and then perform topological sorting using a max-heap, finally reversing the obtained sequence.

Incorrect Condition for Decreasing In-Degree: When relaxing the adjacent nodes, the condition must be strictly written as if (in_degree[v] == 0). If one tries to simplify it to if (in_degree[v] <= 0), although it may not cause issues in most normal graphs, if the original graph has an erroneous state with negative in-degrees due to some graph transformation or concurrent logic, repeatedly pushing into the heap structure could lead to logical vulnerabilities in the algorithm.

Classic NOIP/Luogu Problems

1. Luogu P1347 Sorting

Problem Description: Given $N$ uppercase letters and $M$ relationships of the form A<B, output the order of the letters.

2. Kahn P4017

Problem Description: Given $N$ relationships of the form A<B, determine if there is a cycle and output the topological sorting result.