All problems

Deadlocked Workers

Medium · graph traversal

A warehouse has n workers, numbered 0 to n - 1. Each worker is either free to carry on or is waiting for exactly one other worker to finish something first. The array waits says which: if waits[i] is a worker number, worker i is waiting for that worker, and if waits[i] is -1, worker i is not waiting for anyone.

Workers can end up in a deadlock: a circle of workers who each wait for the next, so none of them can ever move. A worker is deadlocked if, by following "waits for" from that worker again and again, you eventually arrive back at that worker. A worker who waits for themselves is deadlocked too.

A worker who is only waiting for someone in a deadlock is stuck as well, but is not part of the circle and is not counted.

Return the number of deadlocked workers.

Examples

Example 1

Input: waits = [1, 2, 0, -1]

Output: 3

Workers 0, 1 and 2 wait for each other in a circle. Worker 3 waits for nobody.

Example 2

Input: waits = [1, 2, 3, -1]

Output: 0

The waiting forms a line that ends at worker 3, who is free, so there is no circle.

Example 3

Input: waits = [1, 0, 1, 2, 5, 4]

Output: 4

Workers 0 and 1 wait for each other, and so do workers 4 and 5. Workers 2 and 3 are stuck behind the first pair but are not in a circle themselves.

Constraints