1025. Arrows Only Go One Way

A diagram has n boxes and m ARROWS. An arrow points from one box to another and may only be followed in that direction. An arrow may point from a box to itself.

For each of q questions s t, print YES if t can be reached from s by following arrows, and NO otherwise. A box always reaches itself.

``` 3 boxes, arrows 1->2, 3->2

1 to 3 -> NO 3 to 1 -> NO 1 to 2 -> YES ```

3 boxes, arrows 1->2, 2->3 4 boxes, arrows 1->2, 2->3, 3->4, 4->1 1 to 3 -> YES every question -> YES 3 to 1 -> NO

## Why a disjoint set is the wrong tool here, and not merely a slow one

The first example is the whole warning. Feeding both arrows to a disjoint set, which cannot see direction, puts boxes 1, 2 and 3 into one group, so it answers YES to "does 1 reach 3". The right answer is NO, and it is NO in both directions: box 1 reaches only box 2, and box 3 reaches only box 2.

A disjoint set models an EQUIVALENCE: a relation that is reflexive, symmetric and transitive. Reachability along arrows is reflexive and transitive and is NOT symmetric, so it is not an equivalence and there is no way to store it in a structure whose only question is "are these two in the same group". This is not an efficiency problem that a cleverer merge would fix.

It is worth naming what the groups DO mean if you build them anyway: they are the pieces of the diagram with the arrows treated as two-way. That is a genuine and useful thing, and it is an upper bound rather than the answer, because unreachable always implies not in the same group.

## What to use instead

The diagram is fixed and each question is asked once, so answer each one with a plain traversal from s:

for each question (s, t): mark s reached walk out along arrows from every reached box, following each arrow forwards only print YES if t was reached

That is O(n + m) per question, so O(q(n + m)) in total, about 1.4 * 10^7 at these limits, which is why they are in the thousands rather than the hundreds of thousands.

## Why one traversal per question is acceptable here and not always

Nothing is shared between two questions from different starts, so q traversals really do q times the work. At larger q the usual repair is to compute the whole reachability relation once, as n traversals or as n bitsets of n bits each, and answer every question by a lookup. That is O(n(n + m)) or O(n^3 / 64), which is better than O(q(n + m)) only when q is larger than n.

## The box that reaches itself

s equal to t answers YES even with no arrow anywhere. Marking s as reached before the walk begins gets that for free; a check written as "did the walk arrive at t" reports NO.

An arrow from a box to itself changes nothing, since the box already reaches itself.

## Cross-reference

Problem 986 answers connectivity questions on an UNDIRECTED graph as edges arrive, which is exactly where a disjoint set belongs: the relation is symmetric and the graph keeps growing. Both conditions have to hold, and this problem breaks the first one. Problem 400 asks whether every box reaches every other, which is a question about the whole diagram and takes only two traversals rather than n.

## Cost

Time O(q(n + m)). Space O(n + m).

Constraints - `1 ≤ n ≤ 2000` - `0 ≤ m ≤ 5000` - `1 ≤ q ≤ 2000` - `1 ≤ u, v, s, t ≤ n` - `u` may equal `v`, and an arrow may repeat.