Convert undirected connected graph to strongly connected directed graph | Java program for the above approach ; 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
import java . util . * ; import java . lang . * ; class GFG { static ArrayList < int [ ] > ans ; static int flag = 1 ; static int dfs ( ArrayList < ArrayList < Integer > > adj , int [ ] order , int [ ] bridge_detect , boolean [ ] mark , int v , int l ) { mark [ v ] = true ; order [ v ] = order [ l ] + 1 ; bridge_detect [ v ] = order [ v ] ; for ( int i = 0 ; i < adj . get ( v ) . size ( ) ; i ++ ) { int u = adj . get ( v ) . get ( 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 . add ( new int [ ] { v , u } ) ; } if ( bridge_detect [ v ] == order [ v ] && l != 0 ) { flag = 0 ; } return flag ; } static void convert ( ArrayList < ArrayList < Integer > > adj , int n ) { int [ ] order = new int [ n ] ; int [ ] bridge_detect = new int [ n ] ; boolean mark [ ] = new boolean [ n ] ; int flag = dfs ( adj , order , bridge_detect , mark , 1 , 0 ) ; if ( flag == 0 ) { System . out . print ( " - 1" ) ; } else { for ( int [ ] it : ans ) { System . out . println ( it [ 0 ] + " - > " + it [ 1 ] ) ; } } } static void createGraph ( int Edges [ ] [ ] , ArrayList < ArrayList < Integer > > adj , int M ) { for ( int i = 0 ; i < M ; i ++ ) { int u = Edges [ i ] [ 0 ] ; int v = Edges [ i ] [ 1 ] ; adj . get ( u ) . add ( v ) ; adj . get ( v ) . add ( u ) ; } } public static void main ( String [ ] args ) { int N = 5 , M = 6 ; int Edges [ ] [ ] = { { 0 , 1 } , { 0 , 2 } , { 1 , 2 } , { 1 , 4 } , { 2 , 3 } , { 3 , 4 } } ; ArrayList < ArrayList < Integer > > adj = new ArrayList < > ( ) ; ans = new ArrayList < > ( ) ; for ( int i = 0 ; i < N ; i ++ ) adj . add ( new ArrayList < > ( ) ) ; createGraph ( Edges , adj , M ) ; convert ( adj , N ) ; } }