Does the Graph Contain a Bridge?

Given an undirected graph, determine whether it contains at least one bridge. A bridge is an edge whose removal disconnects the graph. Pattern focus: Bridges. This is the boolean version of bridge detection.

Input Format

n = number of vertices, edges = undirected edges [u, v]

Output Format

true if at least one bridge exists, otherwise false

Constraints

  • 1 <= n <= 10^5
  • 1 <= edges.length <= 2 * 10^5

Examples

Example 1:

Input:

n = 4
edges = [[1,2],[2,3],[3,1],[3,4]]

Output:

true

Explanation:

Edge (3,4) is a bridge.

Example 2:

Input:

n = 4
edges = [[1,2],[2,3],[3,1]]

Output:

false

Explanation:

A cycle has no bridge.

Example 3:

Input:

n = 5
edges = [[1,2],[2,3],[3,4],[4,5]]

Output:

true

Explanation:

A path contains bridges.

Loading...
Does the Graph Contain a Bridge?