PreviousNext
Coding/Graphs and trees

Two-edge-connected components

Write codeHard40 min

Your task

Given an undirected graph with n nodes (0..n-1) and edges [u, v], a 2-edge-connected component is a maximal set of nodes that stays connected after the removal of any single edge. Equivalently, delete all bridges and count the resulting connected components. Return that count. Parallel edges may appear. Constraints: 1 <= n <= 2000.

Examples

count_2edge_components(n: int, edges: list[list[int]]) -> int
Example 1
Inputcount_2edge_components(4, [[0, 1], [1, 2], [2, 3]])
Output4