Minimum edges required to make a Directed Graph Strongly Connected | Java program to implement the above approach ; 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
import java . util . * ; class GFG { static void dfs ( int u , Vector < Integer > adj [ ] , int [ ] vis , int [ ] inDeg , int [ ] outDeg ) { vis [ u ] = 1 ; for ( int v : adj [ u ] ) { outDeg [ u ] = 1 ; inDeg [ v ] = 1 ; if ( vis [ v ] == 0 ) { dfs ( v , adj , vis , inDeg , outDeg ) ; } } } static int findMinimumEdges ( int source [ ] , int N , int M , int dest [ ] ) { @ SuppressWarnings ( " unchecked " ) Vector < Integer > [ ] adj = new Vector [ N + 1 ] ; for ( int i = 0 ; i < adj . length ; i ++ ) adj [ i ] = new Vector < Integer > ( ) ; for ( int i = 0 ; i < M ; i ++ ) { adj ] . add ( dest [ i ] ) ; } int inDeg [ ] = new int [ N + 1 ] ; int outDeg [ ] = new int [ N + 1 ] ; int vis [ ] = new int [ N + 1 ] ; dfs ( 1 , adj , vis , inDeg , outDeg ) ; int minEdges = 0 ; int totalIndegree = 0 ; int totalOutdegree = 0 ; for ( int i = 1 ; i <= N ; i ++ ) { if ( inDeg [ i ] == 1 ) totalIndegree ++ ; if ( outDeg [ i ] == 1 ) totalOutdegree ++ ; } minEdges = Math . max ( N - totalIndegree , N - totalOutdegree ) ; return minEdges ; } public static void main ( String [ ] args ) { int N = 5 , M = 5 ; int source [ ] = { 1 , 3 , 1 , 3 , 4 } ; int destination [ ] = { 2 , 2 , 3 , 4 , 5 } ; System . out . print ( findMinimumEdges ( source , N , M , destination ) ) ; } }