1681. Which Tasks Cannot Be Allowed to Slip

A project has n tasks. Task i takes d[i] days. There are m ordering rules, each a b meaning task a must FINISH before task b STARTS. The rules contain no cycle, so the project is schedulable. Any number of tasks may run at the same time, and there is no limit on workers.

Print the earliest day the whole project can finish, then on a second line every CRITICAL task in increasing order. A task is critical when delaying it by even one day delays the whole project.

``` 4 tasks, durations 3 2 4 1 1 before 2, 1 before 3, 2 before 4, 3 before 4

8 1 3 4 ```

Task 1 then 3 then 4 takes 3 + 4 + 1 = 8 days. Task 2 takes 2 days where 4 are available, so it has two days of slack and is not critical.

## The four things that have to be said

directed? yes, and the direction is the whole meaning: a before b. self-loops? impossible: "a before a" would be a cycle. parallel rules? allowed. The same rule stated twice says nothing new. unreachable? nothing is unreachable here, and that is worth stating plainly: every task runs, so there is no sentinel and no -1 case. A task with no rules at all simply starts on day 0. A project may be DISCONNECTED, and then the finish day is decided by whichever piece takes longest. When n is 1 the answer is that task's duration and the task is critical.

## What most people try first

Adding up all the durations, which answers a different question: how long one worker would take. With unlimited workers the answer is the longest CHAIN of dependent tasks, not the total.

The second instinct is to find the longest chain and call its tasks critical. That is right for the finish day and wrong for the list, because several different chains can be longest, and then every task on any of them is critical. On 4 tasks of 5 days each with 1 before 2 and 3 before 4 the finish day is 10 and ALL FOUR tasks are critical, because the two independent chains are both longest.

## Two sweeps over the same topological order

earliest[v] the first day task v can start = max over rules u before v of (earliest[u] + d[u]), or 0 if none finish = max over v of (earliest[v] + d[v]) latest[v] the last day task v can start without delaying the project = (min over rules v before w of latest[w]) - d[v], or finish - d[v] if v has no successor critical every v with latest[v] == earliest[v]

The first sweep runs FORWARD along the topological order, the second BACKWARD along the same order. Nothing has to be sorted twice.

## Why the slack is a difference of two longest paths

earliest[v] is the longest chain of durations finishing before v starts, and finish - latest[v] - d[v] is the longest chain starting after v finishes. The slack latest[v] - earliest[v] is therefore the project length minus the longest chain THROUGH v. It is zero exactly when some longest chain passes through v, which is precisely the condition for a delay there to move the finish day.

That also explains why the critical tasks are not one chain but a UNION of chains, and why they are reported as a sorted set rather than in order of execution.

## The connection to shortest paths

Both sweeps are the single pass of problem 1679 with the weight on the VERTEX instead of the arrow: earliest is a longest path forwards and latest is a longest path backwards. A cycle in the rules would make both meaningless, since a task would have to wait for itself, which is the same reason problem 1679 requires acyclicity.

## Overflow, computed rather than assumed

A chain visits each task at most once, so the finish day is at most n * 10^6 = 5 * 10^10. The limit of a signed 32 bit integer is 2147483647, so every day number here needs 64 bits. One duration of 10^6 fits in 32 bits easily; it is the chain that does not.

## Cost

O(n + m): one topological sort, one forward sweep, one backward sweep, and a linear scan to collect the critical tasks.

Constraints - `1 ≤ n ≤ 50000` - `0 ≤ m ≤ 100000` - `1 ≤ d[i] ≤ 1000000` - `1 ≤ a, b ≤ n` - The ordering rules contain no cycle.