1702. How Many Tasks Can Ever Be Started

A DIRECTED graph has n vertices and m arrows, where u -> v means u must happen before v. Repeatedly remove a vertex that no remaining arrow points at, along with the arrows leaving it. Print how many vertices can be removed this way in total.

chain 1->2->3->4->5 -> 5 all of them chain 1->2->3->4->5 plus 5->3 -> 2 only 1 and 2 cycle 1->2->3->1 -> 0 nothing is ever ready

If the answer is n, nothing was holding anything up and the graph is acyclic. If it is less than n, what remains is holding itself up, and that is a cycle together with everything downstream of it.

## The three things that have to be said

directed? yes. self-loops? allowed, and a self-loop is fatal to its own vertex: u->u means u can never be removed. parallel arrows? allowed, and both copies must be counted. An in-degree of 2 has to be decremented twice. disconnected? allowed. Each piece peels independently.

## What most people try first

The description read literally: scan every remaining vertex, and for each one scan the whole arrow list to see whether anything still points at it. That is O(n m) per removal and O(n^2 m) overall, which at the stated limits is beyond any time limit by many orders of magnitude.

The instinct is right though. What is wrong is RE-DERIVING the in-degrees every round, when removing one vertex only changes the in-degrees of its own out-neighbours.

## Kahn's algorithm

Keep the in-degree array from problem 1701 and a queue of the vertices whose in-degree has already reached 0:

build deg[] and the adjacency list queue = every v with deg[v] == 0 peeled = 0 while queue is not empty: u = pop peeled = peeled + 1 for each arrow u -> v: deg[v] = deg[v] - 1 if deg[v] == 0: push v print peeled

## Why it is correct

Two halves.

A vertex is pushed exactly when its in-degree reaches 0, and the in-degree only ever decreases, by one per arrow, as that arrow's tail is removed. So a vertex is pushed at most once and is pushed as soon as every arrow into it has had its tail removed. That is precisely the condition for it to be removable, so the queue never misses a vertex and never offers one twice.

Nothing left over can be removed, and that is the other half. Suppose some vertices remain. Every one of them still has an arrow in from another remaining vertex, because an arrow from a removed vertex would already have been decremented away. Walk backwards along such arrows: each step stays inside a finite set, so some vertex must repeat, and the stretch between two visits to it is a cycle. A vertex on a cycle can never be ready, since going round the cycle shows it must come after itself.

So peeled == n exactly when there is no directed cycle, and the count is not an approximation of anything.

## Cost

Time O(n + m): each vertex enters the queue at most once and each arrow is examined once, when its tail is popped. Space O(n + m) for the adjacency list, which the constraints force. An adjacency matrix would be 4 * 10^10 entries at n = 2 * 10^5. Nothing overflows: peeled is at most n, and an in-degree is at most m.

## Related

Problem 379 answers Yes or No to whether a cycle exists. This counts how much of the graph the cycle costs, which locates it rather than merely detecting it, and problem 1712 goes one step further and prints the cycle itself.

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