Convert undirected connected graph to strongly connected directed graph | To store the assigned Edges ; Flag variable to check Bridges ; Function to implement DFS Traversal ; Mark the current node as visited ; Update the order of node v ; Update the bridge_detect for node v ; Traverse the adjacency list of Node v ; Ignores if same edge is traversed ; Ignores the edge u -- > v as v -- > u is already processed ; Finds a back Edges , cycle present ; Update the bridge_detect [ v ] ; Else DFS traversal for current node in the adjacency list ; Update the bridge_detect [ v ] ; Store the current directed Edge ; Condition for Bridges ; Return flag ; Function to print the direction of edges to make graph SCCs ; Arrays to store the visited , bridge_detect and order of Nodes ; DFS Traversal from vertex 1 ; If flag is zero , then Bridge is present in the graph ; Else print the direction of Edges assigned ; Function to create graph ; Traverse the Edges ; Push the edges in an adjacency list ; Driver code ; N vertices and M Edges ; To create Adjacency List ; Create an undirected graph ; Function Call
ans = [ ] NEW_LINE flag = 1 ; NEW_LINE def dfs ( adj , order , bridge_detect , mark , v , l ) : NEW_LINE INDENT global flag NEW_LINE mark [ v ] = 1 ; NEW_LINE order [ v ] = order [ l ] + 1 ; NEW_LINE bridge_detect [ v ] = order [ v ] ; NEW_LINE for i in range ( len ( adj [ v ] ) ) : NEW_LINE INDENT u = adj [ v ] [ i ] ; NEW_LINE if ( u == l ) : NEW_LINE INDENT continue ; NEW_LINE DEDENT if ( order [ v ] < order [ u ] ) : NEW_LINE INDENT continue ; NEW_LINE DEDENT if ( mark [ u ] ) : NEW_LINE INDENT bridge_detect [ v ] = min ( order [ u ] , bridge_detect [ v ] ) ; NEW_LINE DEDENT else : NEW_LINE INDENT dfs ( adj , order , bridge_detect , mark , u , v ) ; NEW_LINE DEDENT bridge_detect [ v ] = min ( bridge_detect [ u ] , bridge_detect [ v ] ) ; NEW_LINE ans . append ( [ v , u ] ) ; NEW_LINE DEDENT if ( bridge_detect [ v ] == order [ v ] and l != 0 ) : NEW_LINE INDENT flag = 0 ; NEW_LINE DEDENT return flag ; NEW_LINE DEDENT def convert ( adj , n ) : NEW_LINE INDENT order = [ 0 for i in range ( n ) ] NEW_LINE bridge_detect = [ 0 for i in range ( n ) ] NEW_LINE mark = [ False for i in range ( n ) ] NEW_LINE flag = dfs ( adj , order , bridge_detect , mark , 1 , 0 ) ; NEW_LINE if ( flag == 0 ) : NEW_LINE INDENT print ( - 1 ) NEW_LINE DEDENT else : NEW_LINE INDENT for it in ans : NEW_LINE INDENT print ( " { } ▁ - > ▁ { } " . format ( it [ 0 ] , it [ 1 ] ) ) NEW_LINE DEDENT DEDENT DEDENT def createGraph ( Edges , adj , M ) : NEW_LINE INDENT for i in range ( M ) : NEW_LINE INDENT u = Edges [ i ] [ 0 ] ; NEW_LINE v = Edges [ i ] [ 1 ] ; NEW_LINE adj [ u ] . append ( v ) ; NEW_LINE adj [ v ] . append ( u ) ; NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT N = 5 NEW_LINE M = 6 ; NEW_LINE Edges = [ [ 0 , 1 ] , [ 0 , 2 ] , [ 1 , 2 ] , [ 1 , 4 ] , [ 2 , 3 ] , [ 3 , 4 ] ] ; NEW_LINE adj = [ [ ] for i in range ( N ) ] NEW_LINE createGraph ( Edges , adj , M ) ; NEW_LINE convert ( adj , N ) ; NEW_LINE DEDENT