Nodes on a Loop
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
Nodes 0, 1 and 2 go around in a loop; 3 and 4 can be reached from it but never lead back.
Example 2
The arrows only move forward, so no node can return to itself.
Constraints
1 <= n <= 500 <= len(arrows) <= 1000 <= a, b <= n - 1
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Graphs problems
- Rectangular IslandsMedium
- Rounds of Parallel JobsMedium
- Sealed RoomsMedium
- Smallest Task OrderMedium
- Smallest Team SplitMedium
- Steps to the ExitMedium
- Through the CheckpointMedium
- Towns Within BudgetMedium