1704. Is This Schedule Actually Legal
A DIRECTED graph has n vertices and m arrows, where u -> v means u must
come before v. A candidate order of all n vertices is then given. Print
VALID if every arrow points forwards in it. Otherwise print the 1-based number
of the FIRST arrow in the input that points backwards.
diamond 1->2, 1->3, 2->4, 3->4 order 1 2 3 4 -> VALID
the same diamond order 1 3 2 4 -> VALID
chain 1->2, 2->3 order 2 1 3 -> 1
The first two show why this is a separate question from producing an order: there are usually several valid orders, so a checker cannot work by generating one and comparing.
## The three things that have to be said
directed? yes.
self-loops? allowed, and no order can ever satisfy one: a vertex cannot
come before itself, so a self-loop always fails.
parallel arrows? allowed. Both copies are checked, and the earlier one is
reported if both fail.
disconnected? allowed. Vertices in different pieces are unconstrained.
The candidate is guaranteed to be a permutation of 1 to n, so it is a genuine
order rather than a list that might repeat or omit a vertex.
## What most people try first
Produce a topological order and compare it with the candidate. That fails on the second example above, which is a different valid order of the same graph. Both are legal and a comparison rejects one of them.
The second instinct is to check each arrow by searching the candidate list for
both of its endpoints. That is correct, and it is O(n) per arrow and
O(n m) overall: 4 * 10^10 at the stated limits.
## Invert the order once
An order is a list from POSITION to VERTEX. What the check needs is the opposite direction, from vertex to position:
pos = array of size n + 1
for i = 0 .. n - 1: pos[ order[i] ] = i
Then the whole question is one comparison per arrow:
for i = 1 .. m:
if pos[u_i] >= pos[v_i]: print i and stop
print VALID
## Why >= and not >
The condition for an arrow to be satisfied is pos[u] < pos[v], strictly. Using
> as the failure test would treat pos[u] == pos[v] as acceptable, and that
case does arise: a self-loop u -> u has both positions equal. The test input
1 1 on a single vertex exists for exactly that reason, and a solution using the
strict test prints VALID on a graph where a task is its own prerequisite.
## Why the FIRST failing arrow and not just a No
Reporting the index is what makes the answer useful and what makes it checkable. It also forces the loop to run in input order and to stop at the first failure rather than counting them, and it rules out the shortcut of testing all arrows and reporting any one.
## Cost
Time O(n + m): one pass to invert the order, one pass over the arrows. Space
O(n), and notice no adjacency list is needed at all, because the arrows are
examined once each as they are read. That is the cheapest a graph problem in this
topic gets.
Nothing overflows: a position is less than n and an index is at most m.
Constraints - `1 ≤ n ≤ 200000` - `0 ≤ m ≤ 200000` - `1 ≤ u, v ≤ n` - `u` may equal `v`, so self-loops can occur - the same arrow may be listed more than once - the candidate order is a permutation of 1 to `n` - the graph may be disconnected
Input
The first line contains two integers n and m.
Each of the next m lines contains two integers u and v, an arrow FROM u TO v.
The last line contains n integers, the candidate order from first to last. It is a permutation of 1 to n.
Output
Print either the single word VALID, spelled exactly like that in capitals, or one integer: the 1-based position in the input of the first arrow that points backwards. Print it alone on one line with no other words.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.