Maximum number of bridges in a path of a given graph | Python3 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
N = 100005 NEW_LINE v = [ ] NEW_LINE g = [ ] NEW_LINE vis = [ False ] * ( N ) NEW_LINE In = [ 0 ] * ( N ) NEW_LINE low = [ 0 ] * ( N ) NEW_LINE parent = [ 0 ] * ( N ) NEW_LINE rnk = [ 0 ] * ( N ) NEW_LINE bridges = [ ] NEW_LINE n , m = 6 , 6 NEW_LINE timer = 0 NEW_LINE diameter = 0 NEW_LINE def swap ( x , y ) : NEW_LINE INDENT temp = x NEW_LINE x = y NEW_LINE y = temp NEW_LINE DEDENT def find_set ( a ) : NEW_LINE INDENT global N , v , g , vis , In , low , parent , rnk , bridges , n , m , timer , diameter NEW_LINE if parent [ a ] == a : NEW_LINE INDENT return a NEW_LINE DEDENT parent [ a ] = find_set ( parent [ a ] ) NEW_LINE return parent [ a ] NEW_LINE DEDENT def union_set ( a , b ) : NEW_LINE INDENT global N , v , g , vis , In , low , parent , rnk , bridges , n , m , timer , diameter NEW_LINE x , y = find_set ( a ) , find_set ( b ) NEW_LINE if x == y : NEW_LINE INDENT return NEW_LINE DEDENT if rnk [ x ] == rnk [ y ] : NEW_LINE INDENT rnk [ x ] += 1 NEW_LINE DEDENT if rnk [ y ] > rnk [ x ] : NEW_LINE INDENT swap ( x , y ) NEW_LINE DEDENT parent [ y ] = x NEW_LINE DEDENT def dfsBridges ( a , par ) : NEW_LINE INDENT global N , v , g , vis , In , low , parent , rnk , bridges , n , m , timer , diameter NEW_LINE vis [ a ] = True NEW_LINE timer += 1 NEW_LINE In [ a ] , low [ a ] = timer , timer NEW_LINE for i in range ( len ( v [ a ] ) ) : NEW_LINE INDENT if v [ a ] [ i ] == par : NEW_LINE continue NEW_LINE if vis [ v [ a ] [ i ] ] : NEW_LINE low [ a ] = min ( low [ a ] , In [ v [ a ] [ i ] ] ) NEW_LINE else : NEW_LINE dfsBridges ( v [ a ] [ i ] , a ) NEW_LINE low [ a ] = min ( low [ a ] , low [ v [ a ] [ i ] ] ) NEW_LINE if In [ a ] < low [ v [ a ] [ i ] ] : NEW_LINE INDENT bridges . append ( [ v [ a ] [ i ] , a ] ) NEW_LINE DEDENT else : NEW_LINE INDENT union_set ( v [ a ] [ i ] , a ) NEW_LINE DEDENT DEDENT DEDENT def dfsDiameter ( a , par ) : NEW_LINE INDENT global N , v , g , vis , In , low , parent , rnk , bridges , n , m , timer , diameter NEW_LINE x , y = 0 , 0 NEW_LINE for i in range ( len ( g [ a ] ) ) : NEW_LINE INDENT if g [ a ] [ i ] == par : NEW_LINE continue NEW_LINE mx = dfsDiameter ( g [ a ] [ i ] , a ) NEW_LINE if mx > x : NEW_LINE y = x NEW_LINE x = mx NEW_LINE elif mx > y : NEW_LINE y = mx NEW_LINE DEDENT diameter = max ( diameter , x + y ) NEW_LINE return x + 1 NEW_LINE DEDENT def findMaxBridges ( ) : NEW_LINE INDENT global N , v , g , vis , In , low , parent , rnk , bridges , n , m , timer , diameter NEW_LINE for i in range ( n + 1 ) : NEW_LINE INDENT parent [ i ] = i NEW_LINE rnk [ i ] = 1 NEW_LINE DEDENT dfsBridges ( 1 , 0 ) ; NEW_LINE if len ( bridges ) == 0 : NEW_LINE INDENT return 0 NEW_LINE DEDENT head = - 1 NEW_LINE for i in range ( len ( bridges ) ) : NEW_LINE INDENT a = find_set ( bridges [ i ] [ 0 ] ) NEW_LINE b = find_set ( bridges [ i ] [ 1 ] ) NEW_LINE g [ a ] . append ( b ) NEW_LINE g [ b ] . append ( a ) NEW_LINE head = a NEW_LINE DEDENT diameter = 0 NEW_LINE dfsDiameter ( head , 0 ) NEW_LINE return diameter NEW_LINE DEDENT for i in range ( N ) : NEW_LINE INDENT v . append ( [ ] ) NEW_LINE DEDENT for i in range ( N ) : NEW_LINE INDENT g . append ( [ ] ) NEW_LINE DEDENT v [ 1 ] . append ( 2 ) NEW_LINE v [ 2 ] . append ( 1 ) NEW_LINE v [ 2 ] . append ( 3 ) NEW_LINE v [ 3 ] . append ( 2 ) NEW_LINE v [ 2 ] . append ( 5 ) NEW_LINE v [ 5 ] . append ( 2 ) NEW_LINE v [ 5 ] . append ( 6 ) NEW_LINE v [ 6 ] . append ( 5 ) NEW_LINE v [ 6 ] . append ( 3 ) NEW_LINE v [ 3 ] . append ( 6 ) NEW_LINE v [ 3 ] . append ( 4 ) NEW_LINE v [ 4 ] . append ( 4 ) NEW_LINE ans = findMaxBridges ( ) NEW_LINE print ( ans ) NEW_LINE