FunctionRacerProblemsRace

Critical Junctions

HardGraphsPython, JavaScript, TypeScript, Java, C++

A road map has n junctions numbered 0 to n - 1. roads is a list of pairs [a, b] with a != b, each a two-way road between junctions a and b; the same pair may appear more than once.

A junction is critical when closing it, together with all the roads that touch it, splits the map: afterwards some two other junctions that used to have a route between them have none. Return how many junctions are critical. Return 0 when there is none.

Example 1

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

Closing 2 separates the triangle from 3 and 4; closing 3 strands 4. Closing any other junction splits nothing.

Example 2

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

Close any junction of a triangle and the other two still have their road.

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