1723. Can Any Two Depots Be Ordered

n depots are joined by m one-way routes. Print Yes if EVERY pair of depots can be put in an order, meaning that for every two depots u and v either u reaches v or v reaches u, and No otherwise. One direction is enough; the two do not both have to work.

1->2, 2->3 -> Yes 1->2, 3->2 -> No 1 and 3 reach neither each other 1->2, 2->1, 2->3 -> Yes 1->2, 2->3, 3->1 -> Yes every pair works both ways 4 depots, no routes -> No

This is a weaker demand than problem 400's, which wants every pair to work in BOTH directions. A plain chain satisfies this and fails that.

## The three things that have to be said

directed? yes, and the whole question is about direction. self-loops? allowed, and they change nothing. parallel routes? allowed, and they change nothing. disconnected? allowed, and then the answer is always No for n at least 2, because two depots in different pieces reach neither way.

A single depot answers Yes: there is no pair to check.

## What most people try first

Testing every pair with a search, which is O(n^2(n + m)), or building the transitive closure, which is O(n^3) time and O(n^2) memory. At n = 200000 the closure alone would be 4 * 10^10 bits.

The cheaper wrong idea is to check that the graph is connected when directions are ignored. That is necessary and not sufficient: 1->2, 3->2 is connected that way and still fails.

## Squeeze, then ask for a single file

Squeeze the groups of mutually reachable depots to points, as problem 1720 does, leaving an acyclic graph. Inside a group every pair works both ways, so the question is entirely about the squeezed graph:

the answer is Yes exactly when the squeezed graph has a path visiting every point, that is, when the points form a single file

And that has a startlingly cheap test. List the points in a topological order. If some path visits all of them, that path IS the topological order, and consecutive points must be joined by an arrow. Conversely if every consecutive pair is joined, the order itself is such a path.

order = a topological order of the squeezed graph answer Yes <=> for every i, there is an arrow from order[i] to order[i+1]

## Why checking only consecutive pairs is enough

If consecutive points are joined, then order[i] reaches order[j] for every i < j by stepping along, so every pair of points is comparable and so is every pair of depots. If some consecutive pair is NOT joined, then no path visits everything. Suppose one did; it would be a topological order, and since a topological order of a graph with a spanning path is unique, it would be this one, and then the path would use the arrow between those two consecutive points, which does not exist. Contradiction.

Uniqueness is the load-bearing step: with a spanning path present, no two points are incomparable, so there is never a choice about what comes next.

## No sort is needed

Kosaraju's pass two already hands out group numbers in a topological order, so the check is over the pairs (c, c + 1) for c from 1 to k - 1. Collect the crossing arrows as pairs of group numbers, and look each consecutive pair up. Sorting the pairs once makes the lookups a merge rather than a hash, so nothing is needed beyond O(m log m).

## Cost

Time O(n + m log m), space O(n + m). Searches are iterative, since a path of 200000 depots is permitted and recursion on it overflows Python's recursion limit and the default stack in C, C++ and Java.

## Related

Problem 400 asks for both directions on every pair. Problem 395 asks for a single depot that reaches everyone, which is a question about ONE depot rather than every pair. Problem 1724 asks how many routes would turn this Yes into problem 400's.

Constraints - `1 ≤ n ≤ 200000` - `0 ≤ m ≤ 200000` - `1 ≤ u, v ≤ n` - `u` may equal `v`, so self-loops can occur - the same route may be listed more than once - the map may be disconnected