Minimum edges required to make a Directed Graph Strongly Connected | Perform DFS to count the in - degree and out - degree of the graph ; Mark the source as visited ; Traversing adjacent nodes ; Mark out - degree as 1 ; Mark in - degree as 1 ; If not visited ; DFS Traversal on adjacent vertex ; Function to return minimum number of edges required to make the graph strongly connected ; For Adjacency List ; Create the Adjacency List ; Initialize the in - degree array ; Initialize the out - degree array ; Initialize the visited array ; Perform DFS to count in - degrees and out - degreess ; To store the result ; To store total count of in - degree and out - degree ; Find total in - degree and out - degree ; Calculate the minimum edges required ; Return the minimum edges ; Driver Code ; Function call
function dfs ( u , adj , vis , inDeg , outDeg ) { vis [ u ] = 1 ; for ( var v of adj [ u ] ) { outDeg [ u ] = 1 ; inDeg [ v ] = 1 ; if ( vis [ v ] == 0 ) { dfs ( v , adj , vis , inDeg , outDeg ) ; } } } function findMinimumEdges ( source , N , M , dest ) { var adj = Array . from ( Array ( N + 1 ) , ( ) => Array ( ) ) ; for ( var i = 0 ; i < M ; i ++ ) { adj ] . push ( dest [ i ] ) ; } var inDeg = Array ( N + 1 ) . fill ( 0 ) ; var outDeg = Array ( N + 1 ) . fill ( 0 ) ; var vis = Array ( N + 1 ) . fill ( 0 ) ; dfs ( 1 , adj , vis , inDeg , outDeg ) ; var minEdges = 0 ; var totalIndegree = 0 ; var totalOutdegree = 0 ; for ( var i = 1 ; i <= N ; i ++ ) { if ( inDeg [ i ] == 1 ) totalIndegree ++ ; if ( outDeg [ i ] == 1 ) totalOutdegree ++ ; } minEdges = Math . max ( N - totalIndegree , N - totalOutdegree ) ; return minEdges ; } var N = 5 , M = 5 ; var source = [ 1 , 3 , 1 , 3 , 4 ] ; var destination = [ 2 , 2 , 3 , 4 , 5 ] ; document . write ( findMinimumEdges ( source , N , M , destination ) ) ;