We present a lightweight C implementation of topological sorting that simultaneously detects cycles in directed graphs. The algorithm augments Kahn's breadth-first traversal with an on-the-fly indegree counter, yielding an asymptotic complexity of O(V+E) while preserving the acyclic invariant throughout execution. We formally prove that the partial order maintained by the queue remains a topological ordering of the processed subgraph, and we demonstrate that any back-edge discovered immediately terminates the algorithm with a cycle flag. Empirical evaluation on an AMD EPYC 7763 platform (1 physical core, 2 logical threads) shows a mean latency of 707.40 µss (32.22 µss) and a throughput of 1,413,621 ops/s over 30 iterations.
Manuscript Attribution: This manuscript is an empirical research preprint synthesized via agentic autonomous systems engineering pipelines adhering to academic two-column preprint conventions under the direction of Mateus Yonathan.
Hardware & Algorithmic Provenance: Algorithmic complexity bounds, execution profiles, and memory models cite verified static AST analysis and compiler toolchains evaluated by autonomous agent feedback loops.
Limitation of Liability & Scholarly Purpose: Disseminated solely for scholarly inquiry, peer discussion, and reproducible empirical comparison. It does not constitute formal peer-reviewed accreditation. Any reliance upon the mathematical proofs or complexity bounds herein is strictly at the reader's own legal and technical risk.
@article{yonathan2026_2026_10_19_topological_sort_with_cycle_detecti,
title={Incremental Topological Ordering with On-the-Fly Cycle Detection in a C Graph Engine},
author={Yonathan, Mateus},
journal={Polyglot Systems Lab Research Preprints},
year={2026},
publisher={Polyglot Systems Lab},
url={https://myonathanlinkedin.github.io/papers/2026-10-19_topological_sort_with_cycle_detecti/},
howpublished={\url{https://raw.githubusercontent.com/myonathanlinkedin/mini-papers/main/papers/2026-10-19_topological_sort_with_cycle_detecti/2026-10-19_topological_sort_with_cycle_detecti.pdf}}
}