PreviousNext
Coding/Graphs and trees

Bridge detection

Write codeHard35 minAmazon style

Your task

You are given an undirected graph with n nodes (0..n-1) and a list of undirected edges [u, v]. A bridge is an edge whose removal increases the number of connected components. Return the total number of bridges. The graph may be disconnected and may contain parallel edges (a duplicated edge is never a bridge). Constraints: 1 <= n <= 2000.

Examples

count_bridges(n: int, edges: list[list[int]]) -> int
Example 1
Inputcount_bridges(4, [[0, 1], [1, 2], [2, 3]])
Output3