FunctionRacerProblemsRace

Nodes on a Loop

MediumGraphsPython, JavaScript, TypeScript, Java, C++

A directed graph has n nodes numbered 0 to n - 1. arrows is a list of pairs [a, b], each an arrow from a to b that can only be followed in that direction. The same pair may appear more than once, and an arrow may point from a node to itself.

A node lies on a loop when you can leave it along an arrow and, by following further arrows, come back to it. An arrow from a node to itself puts that node on a loop by itself. Return the number of nodes that lie on at least one loop. Return 0 when there is no loop.

Example 1

n 5
arrows [[0,1],[1,2],[2,0],[2,3],[3,4]]
returns 3

Nodes 0, 1 and 2 go around in a loop; 3 and 4 can be reached from it but never lead back.

Example 2

n 3
arrows [[0,1],[1,2]]
returns 0

The arrows only move forward, so no node can return to itself.

Constraints

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Graphs problems