1768. The Fewest Workers For the Whole Schedule

n jobs must all be done, and m lines say that one job may be followed IMMEDIATELY by another: a line u v means a worker who has just finished u may go straight on to v. The precedence graph is DIRECTED and ACYCLIC.

A worker's day is a chain of jobs, each allowed to follow the one before. Every job must be done by exactly one worker. Print the fewest workers needed.

A chain may be a single job, so the answer is never more than n.

1->2, 2->3 -> 1 one worker does 1, 2, 3 1->2, 1->3 -> 2 after job 1 a worker can take 2 or 3, not both no arcs at all -> n everyone works alone

## What most people try first

Count the jobs with no incoming arc, on the reasoning that every chain starts at one. It is wrong in both directions. 1->2, 1->3 has one such job and needs two workers. And a job with an incoming arc can still have to start a chain, because the predecessor may be busy being followed by somebody else.

The second attempt is the longest chain: find the longest path and subtract. The answer is not n minus the longest path either, because the chains have to be DISJOINT and the longest path may not be part of any best set of chains.

1->3, 2->3, 3->4, 3->5

The longest path has 3 jobs (1->3->4), so "n minus longest plus 1" guesses 3. The real answer is 3 as well here, but on 1->2, 1->3, 4->2, 4->3 the longest path has 2 jobs and that formula guesses 3, while the answer is 2: one worker does 1, 2 and the other does 4, 3.

## The method

Each job may be followed by at most ONE job, and may follow at most ONE job, because a worker goes somewhere definite next and comes from somewhere definite before. So choosing the chains is choosing a set of arcs with no repeated tail and no repeated head. That is a matching between two copies of the jobs:

left copy = job as a PREDECESSOR (its chain continues to something) right copy = job as a SUCCESSOR (its chain came from something) arc u->v = pair (left u, right v)

With k arcs chosen the n jobs split into n - k chains, because each chosen arc joins two chains into one and the choices never form a cycle: the graph is acyclic, so a cycle of chosen arcs is impossible, and a branch is impossible because no tail and no head repeats. So

answer = n - (largest matching)

Build the matching as a flow exactly as problem 1763 does, with a source feeding each left copy at capacity 1, each right copy feeding a sink at capacity 1, and each arc a capacity-1 link between the copies.

## Why acyclicity is needed

Without it, 1->2, 2->1 has a matching of size 2 and the formula would say 0 chains, which is nonsense: those two arcs form a closed loop and no worker's day is a loop. On a DAG that cannot happen, which is why the constraint is stated rather than assumed.

## The three things that have to be said

directed? yes, and acyclic. self-loops? cannot occur, since a self-loop is a cycle of length 1. parallel arcs? allowed, and a repeat changes nothing, because the left copy of u still admits one unit. disconnected? allowed, and the answer simply adds up over the pieces.

## Cost

The network has 2n + 2 nodes and 2n + m arcs, and the matching is at most n, so Edmonds-Karp does at most n rounds of O(n + m): about 300 * 3600 = 1.1 * 10^6 at the limits. The answer is between 1 and n, so at most 300, and nothing here approaches 2147483647.

Constraints - `1 ≤ n ≤ 300` - `0 ≤ m ≤ 3000` - `1 ≤ u, v ≤ n` - the graph is DIRECTED and ACYCLIC, so no self-loop can occur - the same pair may be listed more than once, and a repeat changes nothing - the graph may be disconnected