Find the critical path of a task network.
Input: first line n; then n lines TASK duration dep1,dep2,... (or - for no dependencies). Tasks may be listed in any order; every dependency is one of the n tasks and there are no cycles.
Compute for each task its earliest finish EF = duration + max(EF of its dependencies) (0 if none). The project duration is the largest EF. The critical path is built backwards: start from the task with the largest EF (first in input order on a tie); repeatedly go to the dependency with the largest EF (first in that task's dependency list on a tie) until a task with no dependencies.
Output:
TASK: EF=x
... (all tasks in input order)
Project duration: D days
Critical path: A -> C -> E -> F
Slack: TASK=s, TASK=s, ...
Slack lists, in input order, every task not on the critical path with its slack, computed as LF − EF, where the latest finish LF of a task is the minimum over its successors of (LF of successor − duration of successor), and D for tasks with no successors. Print Slack: none if all tasks are critical.
Input:
6
A 3 -
B 4 A
C 5 A
D 6 -
E 7 C,D
F 1 B,E
Output:
A: EF=3
B: EF=7
C: EF=8
D: EF=6
E: EF=15
F: EF=16
Project duration: 16 days
Critical path: A -> C -> E -> F
Slack: B=8, D=2