382. Minimum Time for Each Job in a DAG

Given a directed acyclic graph with n jobs (0-indexed) and m edges, where an edge u->v means job v can only start once job u has finished, and every job takes exactly 1 unit of time to run, find the earliest time each job can finish (a job with no prerequisites finishes at time 1). Print the n completion times, space-separated, in job order.

Input: The first line contains an integer n, the number of jobs. The second line contains an integer m, the number of edges. Each of the next m lines contains two space-separated integers u and v, meaning job v depends on job u. Output: Print n space-separated integers - the earliest completion time of each job in job order.

1 <= n <= 10^5

TAKING THE MAX (not overwriting) when relaxing a job's completion time is essential - a job with MULTIPLE prerequisites must wait for the LATEST of them to finish, not just whichever one happened to be processed most recently.

Given jobs with prerequisite dependencies (each taking 1 unit of time), find the earliest each job can finish. Brute force: Recursively compute each job's completion time by fully re-deriving all of its prerequisites' times from scratch every time - this recomputes the SAME sub-results repeatedly for jobs with shared prerequisites, unless memoized or processed in the right order. Optimised: Processing jobs in TOPOLOGICAL order guarantees every prerequisite is fully finalized before its dependents are computed, letting each job's completion time be computed exactly ONCE using already-known prerequisite times - no memoization or recomputation needed beyond the natural ordering itself.

Compute in-degrees for all jobs, seed a queue with every job that has in-degree zero (finish time 1), then repeatedly pop a job, and for each of its outgoing edges decrement the neighbor's in-degree, setting the neighbor's finish time to the current job's finish time + 1 (keeping the maximum if reached from multiple predecessors) and enqueuing it once its in-degree hits zero. This is correct because Kahn's algorithm processes jobs in a valid topological order naturally as part of the BFS itself, so finish times can be computed inline in the same forward pass, without ever needing to build a separate reversed graph or a distinct topological-sort step beforehand. Time: O(V + E) Space: O(V)

First build the reverse graph (an edge v->u for every original edge u->v) and compute a topological ordering of the jobs via DFS with a finish-order stack. Then process the jobs in topological order, computing each job's finish time as 1 plus the maximum finish time among all of its predecessors, looked up via the reverse graph's adjacency lists. This is correct because processing jobs in topological order guarantees every prerequisite is finalized before it's needed, but it requires the extra step and memory of explicitly constructing the reversed graph before the actual computation can begin. Time: O(V + E) Space: O(V + E)

Initialize every job's finish time to 1, then repeatedly loop over every edge u->v in the graph and update finish[v] to max(finish[v], finish[u] + 1) whenever that would increase it, repeating this full pass over all edges up to n times or until nothing changes. This is correct because in a DAG, enough rounds of relaxation are guaranteed to propagate the correct longest-path-based finish time to every node, similar to Bellman-Ford, but it does not exploit the DAG structure and instead brute-forces convergence through possibly many redundant full passes over all edges. Time: O(V * E) Space: O(V)

1. A job's completion time is 1 PLUS the MAXIMUM completion time among all of its direct prerequisites (or just 1 if it has none). 2. Process jobs in TOPOLOGICAL ORDER (Kahn's algorithm works well) so every prerequisite's time is already finalized by the time you need it. 3. RELAX a job's completion time every time a new prerequisite of it gets processed, taking the MAX rather than overwriting, since a job can have several prerequisites finishing at different times.

Time: O(n + m) - one topological sort plus one relaxation pass over all edges. Space: O(n), for the completion-time array and the topological order.

a job with no prerequisites (completion time 1), a job with multiple prerequisites finishing at different times (must take the max), and n at its maximum of 10^5 to confirm the topological computation runs efficiently.

Be ready to connect this directly to 'Longest Path in a DAG' - this problem is essentially a specialized version where every edge has weight 1 (since every job takes exactly one unit of time), and 'completion time' is really just 'longest path length from any starting point to this job, plus 1'.