FunctionRacerProblemsRace

Mutual Reach Groups

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. Node a reaches node b when b can be found by following zero or more arrows from a, so every node reaches itself.

Two nodes belong to the same group when each reaches the other. Every node belongs to exactly one group. Return the number of groups. With no arrows the answer is n.

Example 1

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

Nodes 0, 1 and 2 all reach each other; 3 and 4 can be reached from them but cannot get back, and 4 cannot reach 3.

Example 2

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

No two nodes reach each other both ways, so every node is a group of its own.

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