1709. Is the Schedule Forced
A directed graph of n tasks with m prerequisite arrows is given, and it is
guaranteed to contain no cycle, so at least one legal order exists. Print Yes
if there is EXACTLY ONE legal order, and No if there are two or more.
1->2 2->3 3->4 Yes the order is forced: 1 2 3 4
1->2 1->3 No 2 and 3 may come in either order
n = 2, no arrows No either task may go first
n = 1, no arrows Yes one task, one order
## What most people try first
Generate the orders and count them. At n = 20 a graph with no arrows has
20! orders, about 2.4 * 10^18, so counting cannot be the method even when
the answer is "two or more". The question has to be settled without producing a
second order.
A more careful attempt runs the topological sort twice with different tie-breaks and compares. That is closer, and it is still not a proof: two runs agreeing tells you those two agreed, not that no third order exists.
## Watch what Kahn's algorithm does at each step
Kahn's algorithm repeatedly takes a task whose prerequisites are all done. The set of such tasks is the CHOICE available at that moment.
ready = every task with in-degree 0
while ready is not empty:
if ready holds more than one task: the order is not forced
take the single task x, and reduce the in-degree of everything x points to
So the answer is Yes exactly when ready holds exactly one task at every
step.
## Why one choice per step is the whole condition
If every step offers one task, then the algorithm had no freedom anywhere, so the
order it produced is the only one, and the answer is Yes.
If some step offers two tasks a and b, then neither is a prerequisite of the
other, because both have all prerequisites already done at that moment. So
taking a then b, or b then a, both extend to complete legal orders, and
they differ. That gives two orders, so the answer is No.
Both directions are therefore settled by a single pass, with no order ever compared against another.
## The same condition, stated differently
The order is forced exactly when the unique order forms a PATH: every
consecutive pair in it is joined by an arrow. If a gap existed between two
consecutive tasks, they could be swapped. That phrasing is worth knowing because
it is how the condition is usually recognised in an interview, and it is why a
graph on n tasks needs at least n - 1 arrows to force its order.
## The boundaries
n = 1 with no arrows answers Yes: one task has exactly one order. n = 2
with no arrows answers No. A solution that reports Yes whenever the sort
succeeds gets both of these wrong, since the sort succeeds on every acyclic
graph.
## Cost
O(n + m), one pass of Kahn's algorithm with a counter.
Constraints - `1 ≤ n ≤ 200000` - `0 ≤ m ≤ 200000` - `1 ≤ u, v ≤ n` and `u` is not equal to `v` - the graph contains no cycle - the same arrow may appear more than once
Input
The first line contains two integers n and m.
Each of the next m lines contains two integers u and v, meaning task u must come before task v.
The graph is guaranteed to contain no cycle. It may be disconnected.
Output
Print exactly one word on its own line: Yes if there is exactly one legal order of all n tasks, or No if two or more legal orders exist.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.