Maximum number of bridges in a path of a given graph | Javascript program to find the maximum number of bridges in any path of the given graph ; Stores the nodes and their connections ; Store the tree with Bridges as the edges ; Stores the visited nodes ; For finding bridges ; for Disjoint Set Union ; For storing actual bridges ; Stores the number of nodes and edges ; For finding bridges ; Function to find root of the component in which A lies ; Doing path compression ; Function to do union between a and b ; If both are already in the same component ; If both have same rank , then increase anyone 's rank ; Function to find bridges ; Initialize in time and low value ; Update the low value of the parent ; Perform DFS on its child updating low if the child has connection with any ancestor ; Bridge found ; Otherwise ; Find union between parent and child as they are in same component ; Function to find diameter of the tree for storing max two depth child ; Finding max two depth from its children ; Update diameter with the sum of max two depths ; Return the maximum depth ; Function to find maximum bridges bwtween any two nodes ; DFS to find bridges ; If no bridges are found ; Iterate over all bridges ; Find the endpoints ; Generate the tree with bridges as the edges ; Update the head ; Return the diameter ; Graph = > 1 -- -- 2 -- -- 3 -- -- 4 | | 5 -- -- 6
let N = 1e5 + 5 ; let v = new Array ( N ) ; let g = new Array ( N ) ; let vis = new Array ( N ) ; let In = new Array ( N ) ; let low = new Array ( N ) ; let parent = new Array ( N ) ; let rnk = new Array ( N ) ; let bridges = [ ] ; let n , m ; let timer = 0 ; let diameter ; function swap ( x , y ) { let temp = x ; x = y ; y = temp ; } function find_set ( a ) { if ( parent [ a ] == a ) return a ; return parent [ a ] = find_set ( parent [ a ] ) ; } function union_set ( a , b ) { let x = find_set ( a ) , y = find_set ( b ) ; if ( x == y ) return ; if ( rnk [ x ] == rnk [ y ] ) rnk [ x ] ++ ; if ( rnk [ y ] > rnk [ x ] ) swap ( x , y ) ; parent [ y ] = x ; } function dfsBridges ( a , par ) { vis [ a ] = true ; In [ a ] = low [ a ] = timer ++ ; for ( let i = 0 ; i < v [ a ] . length ; i ++ ) { if ( v [ a ] [ i ] == par ) continue ; if ( vis [ v [ a ] [ i ] ] ) low [ a ] = Math . min ( low [ a ] , In [ v [ a ] [ i ] ] ) ; else { dfsBridges ( v [ a ] [ i ] , a ) ; low [ a ] = Math . min ( low [ a ] , low [ v [ a ] [ i ] ] ) ; if ( In [ a ] < low [ v [ a ] [ i ] ] ) bridges . push ( [ v [ a ] [ i ] , a ] ) ; else union_set ( v [ a ] [ i ] , a ) ; } } } function dfsDiameter ( a , par ) { let x = 0 , y = 0 ; for ( let i = 0 ; i < g [ a ] . length ; i ++ ) { if ( g [ a ] [ i ] == par ) continue ; let mx = dfsDiameter ( g [ a ] [ i ] , a ) ; if ( mx > x ) { y = x ; x = mx ; } else if ( mx > y ) y = mx ; } diameter = Math . max ( diameter , x + y ) ; return x + 1 ; } function findMaxBridges ( ) { for ( let i = 0 ; i <= n ; i ++ ) { parent [ i ] = i ; rnk [ i ] = 1 ; } dfsBridges ( 1 , 0 ) ; if ( bridges . length == 0 ) return 0 ; let head = - 1 ; for ( let i = 0 ; i < bridges . length ; i ++ ) { let a = find_set ( bridges [ i ] [ 0 ] ) ; let b = find_set ( bridges [ i ] [ 1 ] ) ; g [ a ] . push ( b ) ; g [ b ] . push ( a ) ; head = a ; } diameter = 0 ; dfsDiameter ( head , 0 ) ; return diameter ; } n = 6 ; m = 6 ; for ( let i = 0 ; i < v . length ; i ++ ) v [ i ] = [ ] ; for ( let i = 0 ; i < g . length ; i ++ ) g [ i ] = [ ] ; v [ 1 ] . push ( 2 ) ; v [ 2 ] . push ( 1 ) ; v [ 2 ] . push ( 3 ) ; v [ 3 ] . push ( 2 ) ; v [ 2 ] . push ( 5 ) ; v [ 5 ] . push ( 2 ) ; v [ 5 ] . push ( 6 ) ; v [ 6 ] . push ( 5 ) ; v [ 6 ] . push ( 3 ) ; v [ 3 ] . push ( 6 ) ; v [ 3 ] . push ( 4 ) ; v [ 4 ] . push ( 4 ) ; let ans = findMaxBridges ( ) ; document . write ( ans + " " ) ;