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 ; N vertices and M Edges ; To create Adjacency List ; Create an undirected graph ; Function Call
let ans ; let flag = 1 ; function dfs ( adj , order , bridge_detect , mark , v , l ) { mark [ v ] = true ; order [ v ] = order [ l ] + 1 ; bridge_detect [ v ] = order [ v ] ; for ( let i = 0 ; i < adj [ v ] . length ; i ++ ) { let u = adj [ v ] [ i ] ; if ( u == l ) { continue ; } if ( order [ v ] < order [ u ] ) { continue ; } if ( mark [ u ] ) { bridge_detect [ v ] = Math . min ( order [ u ] , bridge_detect [ v ] ) ; } else { dfs ( adj , order , bridge_detect , mark , u , v ) ; } bridge_detect [ v ] = Math . min ( bridge_detect [ u ] , bridge_detect [ v ] ) ; ans . push ( [ v , u ] ) ; } if ( bridge_detect [ v ] == order [ v ] && l != 0 ) { flag = 0 ; } return flag ; } function convert ( adj , n ) { let order = new Array ( n ) ; let bridge_detect = new Array ( n ) ; let mark = new Array ( n ) ; let flag = dfs ( adj , order , bridge_detect , mark , 1 , 0 ) ; if ( flag == 0 ) { document . write ( " " ) ; } else { for ( let it = 0 ; it < ans . length - 1 ; it ++ ) { document . write ( ans [ it ] [ 0 ] + " " + ans [ it ] [ 1 ] + " " ) ; } } } function createGraph ( Edges , adj , M ) { for ( let i = 0 ; i < M ; i ++ ) { let u = Edges [ i ] [ 0 ] ; let v = Edges [ i ] [ 1 ] ; adj [ u ] . push ( v ) ; adj [ v ] . push ( u ) ; } } let N = 5 , M = 6 ; let Edges = [ [ 0 , 1 ] , [ 0 , 2 ] , [ 1 , 2 ] , [ 1 , 4 ] , [ 2 , 3 ] , [ 3 , 4 ] ] ; let adj = [ ] ; ans = [ ] ; for ( let i = 0 ; i < N ; i ++ ) adj . push ( [ ] ) ; createGraph ( Edges , adj , M ) ; convert ( adj , N ) ;