CODEWITHSUNDEEP
algorithmgraph
user123454321
user123454321

Reputation: 1058

Bridge in unidirected graph

I am thinking of easiest way to check if two vertices (edge) is a bridge in unidirected graph G? My graph is represented by adjecency list.

Upvotes: 0

Views: 82

Answers (1)

Juan Lopes
Juan Lopes

Reputation: 10595

(The easiest to understand isn't necessarily the best way.)

Run DFS and count the number of components. Remove the edge and run the DFS again. If the number of components increased, that was a bridge.

Upvotes: 1

Related Questions