383. Course Schedule - Possible to Finish All Tasks

There are n tasks (0-indexed) and m dependency pairs, each given as 'a b' meaning task a can only be attempted once task b is finished. Print 'Yes' if it's possible to finish every task (given some valid order), otherwise print 'No'.

Input: The first line contains an integer n, the number of tasks. The second line contains an integer m, the number of dependency pairs. Each of the next m lines contains two space-separated integers a and b, meaning task a depends on task b. Output: Print 'Yes' if all tasks can be finished, otherwise print 'No'.

1 <= n <= 10^5

This is one of the most practical, real-world-motivated applications of topological sort and cycle detection - literally the same technique used by real build systems and package managers to detect circular dependencies.

Given tasks with dependency requirements, check whether it's possible to complete all of them. Brute force: Try every possible ordering of tasks and check if it satisfies every dependency - this is factorial time, impractical for large n, when Kahn's algorithm directly determines feasibility. Optimised: Kahn's algorithm's own completion condition doubles as exactly the answer needed here - if it can remove every single task (following in-degree-0 availability), a valid completion order exists; if it gets stuck with tasks remaining, those tasks are unavoidably part of a circular dependency, making completion impossible.

Compute the in-degree of every task from the dependency list, and push every task with in-degree 0 into a queue. Repeatedly pop a task from the queue, count it as processed, and decrement the in-degree of every task that depends on it, pushing any task whose in-degree drops to 0 into the queue. If the total count of processed tasks reaches n, every task can be completed in some valid order, so print 'Yes'; otherwise the tasks still stuck with positive in-degree belong to a dependency cycle, so print 'No'. This avoids recursion entirely and directly builds a valid finishing order when one exists. Time: O(n + m) Space: O(n)

Run one DFS traversal over the whole graph, keeping a 'currently on recursion stack' marker for each task in addition to a 'fully finished' marker. Whenever the DFS follows a dependency edge into a task that is already marked as being on the current recursion stack, a back edge (and hence a cycle) has been found, meaning it's impossible to finish all tasks, so print 'No'. If the DFS completes over every task without ever hitting such a back edge, print 'Yes'. A single traversal with proper state tracking replaces the repeated per-task traversals of the brute approach. Time: O(n + m) Space: O(n)

Build the dependency graph as an adjacency list, then for every one of the n tasks independently run a DFS or BFS following dependency edges to see whether that traversal ever leads back to the starting task; if it ever does for any task, a cycle exists and finishing all tasks is impossible, so print 'No'. If none of the n independent traversals ever revisits their own starting task, print 'Yes'. This checks cycle existence directly from the definition but repeats a full graph traversal once per task. Time: O(n * (n + m)) Space: O(n + m)

1. View this as CYCLE DETECTION on the dependency graph (a directed graph where an edge means 'depends on'). 2. Use Kahn's algorithm: repeatedly remove tasks with IN-DEGREE 0 (nothing left blocking them), decrementing their dependents' in-degrees. 3. If you're able to remove ALL n tasks this way, every task is finishable; if some remain stuck (all having in-degree > 0), those remaining tasks are part of an unresolvable cycle.

Time: O(n + m) - Kahn's algorithm processes every vertex and edge exactly once. Space: O(n), for the in-degree array and the queue of available tasks.

m = 0 (no dependencies), a cycle among the dependencies (answer 'No'), and n at its maximum of 10^5 to confirm Kahn's algorithm runs efficiently.

Be ready to connect this directly to 'Topological Sort' - this is literally the exact same algorithm, just asking a yes/no feasibility question (can all n vertices be processed) rather than requesting the actual order itself.