Minimum edges required to make a Directed Graph Strongly Connected | C # 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
using System ; using System . Collections . Generic ; class GFG { static void dfs ( int u , List < int > [ ] adj , int [ ] vis , int [ ] inDeg , int [ ] outDeg ) { vis [ u ] = 1 ; foreach ( int v in 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 ) { List < int > [ ] adj = new List < int > [ N + 1 ] ; for ( int i = 0 ; i < adj . Length ; i ++ ) adj [ i ] = new List < int > ( ) ; 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 } ; Console . Write ( findMinimumEdges ( source , N , M , destination ) ) ; } }