1713. Which Tasks Never Get Going

n tasks are numbered 1 to n. An arrow u -> v means task u must FINISH before task v may START. A task may start once every arrow pointing at it comes from a task that has already finished.

Print, in increasing order, every task that can never start. Print None if every task can.

1->2, 2->3, 3->2, 3->4 -> 2 3 4 1->2, 2->3 -> None 1->1 -> 1

In the first example task 1 starts immediately and finishes. Tasks 2 and 3 wait for each other forever, and task 4 waits for task 3, so three tasks are stuck.

## The three things that have to be said

directed? yes. u -> v constrains v only. self-loops? allowed. u -> u means u waits for itself, so u never starts. parallel arrows? allowed. Three copies of 1 -> 2 are three separate waits. disconnected? allowed. A task no arrow touches starts immediately.

The parallel case is the one that catches solutions. A task with three copies of the same incoming arrow has three prerequisites to discharge, not one, and a solution that stores neighbours in a set reports it as permanently stuck. There is a test below that is exactly that graph.

## What most people try first

Walk forward from every task with nothing pointing at it and mark what you reach. That is wrong in a direction worth seeing: reaching a task is not the same as being allowed to start it. On 1->3, 2->3, 2->2 the walk from task 1 reaches task 3, but task 3 also waits on task 2, which never finishes, so task 3 is stuck.

Being startable is a condition on ALL the arrows into a task, so it cannot be decided by a walk that arrives along one of them.

## Peel the ready tasks off, one at a time

Count the arrows into each task. A task with a count of 0 can start now. Starting it and finishing it discharges one wait on each task it points at, so decrement those counts, and any that reach 0 joins the ready list.

indeg[v] = number of arrows into v ready = every v with indeg[v] == 0 while ready is not empty: take x out of ready for each arrow x -> y: indeg[y] -= 1; if indeg[y] == 0: add y to ready

Whatever is left with a positive count when the list empties is the answer.

## Why that is exactly the right set

A task released by the loop clearly can start: the loop only releases it after every arrow into it came from a released task, and by induction every one of those really does finish.

The other direction is the interesting half. Suppose some task is never released. Look at the set S of unreleased tasks. Every task in S still has an undischarged arrow into it, and that arrow must come from inside S, because every task outside S was released and discharged all of its arrows. So every task in S has an incoming arrow from S, which means following arrows backwards inside S never stops, which means S contains a cycle. A task on a cycle genuinely cannot start, and neither can anything waiting on one.

That is the whole statement: the stuck tasks are the cycles together with everything downstream of them.

## Related

Problem 1702 counts how many tasks can ever be started on the same input. This prints which ones cannot, and the two answers add up to n. Problem 1704 checks whether a schedule someone proposes is legal, and problem 1712 prints a cycle once one is known to exist.

## Cost

Time O(n + m): each task enters the ready list at most once and each arrow is examined once. Space O(n + m) for the adjacency lists and the counts. Keep the loop a loop: a chain of 200000 tasks is permitted, so a recursive release would overflow Python's recursion limit and the default stack elsewhere. Nothing overflows a 32-bit integer, since no count exceeds m = 200000.

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