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
#include <bits/stdc++.h> NEW_LINE using namespace std ; void dfs ( int u , vector < int > adj [ ] , int * vis , int * inDeg , int * outDeg ) { vis [ u ] = 1 ; for ( auto v : adj [ u ] ) { outDeg [ u ] = 1 ; inDeg [ v ] = 1 ; if ( vis [ v ] == 0 ) { dfs ( v , adj , vis , inDeg , outDeg ) ; } } } int findMinimumEdges ( int source [ ] , int N , int M , int dest [ ] ) { vector < int > adj [ N + 1 ] ; for ( int i = 0 ; i < M ; i ++ ) { adj [ source [ i ] ] . push_back ( dest [ i ] ) ; } int inDeg [ N + 1 ] = { 0 } ; int outDeg [ N + 1 ] = { 0 } ; int vis [ N + 1 ] = { 0 } ; 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 = max ( N - totalIndegree , N - totalOutdegree ) ; return minEdges ; } int main ( ) { int N = 5 , M = 5 ; int source [ ] = { 1 , 3 , 1 , 3 , 4 } ; int destination [ ] = { 2 , 2 , 3 , 4 , 5 } ; cout << findMinimumEdges ( source , N , M , destination ) ; return 0 ; }