##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
(Linear time solution)
The time complexity is . Topological sort takes , and processing vertices takes total because you check each edge once.
The space complexity is for the boolean array and for the graph representation. This is efficient. Even for large DAGs, this algorithm runs quickly. You process each vertex and each edge exactly once, making this optimal for the problem.
