CODEWITHSUNDEEP
graphbridge
satyres
satyres

Reputation: 377

Finding Bridges in undirected Graph?

A bridge in a graph means if we remove it the graph will be disconnected ! so i want to know if there is way to find all bridges in a graph : here is an example :

input
    12 15
    1 2
    1 3
    2 4
    2 5
    3 5
    4 6
    6 7
    6 10
    6 11
    7 8
    8 9
    8 10
    9 10
    10 11
    11 12

Output :

    2 4
    4 6
    11 12

PLEASE DO NOT GIVE ME THE SOLUTION JUST A HINT ! Thanks

Upvotes: 1

Views: 2475

Answers (1)

Prasanth Jayachandran
Prasanth Jayachandran

Reputation: 570

If you have the visiting number vn[v] and low number low[v] for each vertex v in graph G, then you can find if an edge is bridge of not (while unwinding the dfs recursive calls) using the following condition

if (low[w] > vn[v]) then (v,w) is a bridge

Upvotes: 5

Related Questions