Time and Space Complexity

Time Complexity:

• O(V² + E) as written here, because each of the V rounds scans all vertices to find the smallest in-degree-0 one. With a priority queue it improves to O((V + E) log V), and with a plain queue (any valid order) to O(V + E).

Space Complexity:

• O(V + E) for the adjacency list, in-degree array, and output.

Summary:

• Topological Sort orders a DAG so every edge points forward, using in-degrees and Kahn's algorithm.
• If not all vertices can be placed, the graph contains a cycle.