1716. Can Every Job Come Round Again

n jobs are numbered 1 to n, and m arrows record that job u can hand work straight on to job v. Print Yes if EVERY job lies on at least one cycle, meaning work handed out of it can come back to it, and No otherwise.

1->2, 2->3, 3->1 -> Yes 1->2, 2->3 -> No nothing returns to job 1 1->2, 2->1, 3->4, 4->3 -> Yes two separate cycles, both closed 1->1 -> Yes a job handing work to itself 1->2, 1->2 -> No a repeated arrow is not a return path

## The three things that have to be said

directed? yes, and that is the whole question. self-loops? allowed, and u -> u puts u on a cycle of length one. parallel arrows? allowed, and two copies of u -> v are still both one way. disconnected? allowed. Every piece must satisfy the condition separately.

The parallel case is worth dwelling on. Two arrows 1 -> 2 give vertex 1 an out-degree of 2 and vertex 2 an in-degree of 2, so a solution that checks only "every vertex has an arrow in and an arrow out" says Yes. There is no way back from 2 to 1, so the answer is No. That graph is one of the tests.

## What most people try first

Checking that no vertex has in-degree 0 and no vertex has out-degree 0. It is necessary and it is not sufficient, and the repeated-arrow graph above is the smallest counterexample. Degrees are local; being on a cycle is not.

The next attempt is to search from each job and see whether it comes back. That is correct and it is O(n(n + m)), too slow at n = m = 200000.

## Restate it as a question about groups

Group the jobs by mutual reachability, as problem 1715 does. Then:

job v lies on a cycle <=> v's group holds at least two jobs, or v has a self-loop

Forwards: if the group holds another job w, then v reaches w and w reaches v, and joining those two walks gives a closed walk through v of length at least 1, which contains a cycle through v. A self-loop is such a walk directly.

Backwards: if v is on a cycle of length at least 2, every other vertex on that cycle is mutually reachable with v, so the group is not a singleton. If the cycle has length 1 it is a self-loop. So nothing else qualifies, and a singleton group with no self-loop genuinely has no way home.

So compute the groups once with Kosaraju's two passes, count their sizes, note which jobs carry a self-loop, and answer in a single sweep.

## Related

Problem 365 asks only whether SOME cycle exists. Problem 1712 prints one. Problem 1713 finds the jobs that can never start, which is the opposite condition applied to a schedule. This one insists every job is on a cycle, which is the condition under which a system can run forever.

## Cost

Time O(n + m): two searches plus two linear sweeps. Space O(n + m). Both searches carry an explicit stack, since a path of 200000 vertices is permitted and recursion on it overflows Python's recursion limit and the default stack in C, C++ and Java.

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 graph may be disconnected