FunctionRacerProblemsRace

Count the Bridges

HardGraphsPython, JavaScript, TypeScript, Java, C++

A network has n nodes numbered 0 to n - 1. links is a list of pairs [a, b] with a != b, each a link that carries traffic both ways. The same pair may appear more than once, and every copy is a separate link.

A link is a bridge when removing that single link, while keeping every other link, leaves some two nodes that could reach each other before no longer able to. Because of this, two copies of the same pair are never bridges. Return the number of bridges. Return 0 when there is none.

Example 1

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

Nodes 0, 1 and 2 form a triangle, so none of its links is a bridge; the links [2, 3] and [3, 4] are the only way to reach 3 and 4.

Example 2

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

Every link of a triangle has a way around it.

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