Minimum number of reversals to reach node 0 from every other node | C ++ program for the above approach ; Function to find minimum reversals ; Add all adjacent nodes to the node in the graph ; Insert edges in the graph ; Insert edges in the reversed graph ; Create array visited to mark all the visited nodes ; Stores the number of edges to be reversed ; BFS Traversal ; Pop the current node from the queue ; mark the current node visited ; Intitialize count of edges need to be reversed to 0 ; Push adjacent nodes in the reversed graph to the queue , if not visited ; Push adjacent nodes in graph to the queue , if not visited count the number of nodes added to the queue ; Update the reverse edge to the final count ; Return the result ; Driver Code ; Given edges to the graph ; Number of nodes ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int minRev ( vector < vector < int > > edges , int n ) { unordered_map < int , vector < int > > graph ; unordered_map < int , vector < int > > graph_rev ; for ( int i = 0 ; i < edges . size ( ) ; i ++ ) { int x = edges [ i ] [ 0 ] ; int y = edges [ i ] [ 1 ] ; graph [ x ] . push_back ( y ) ; graph_rev [ y ] . push_back ( x ) ; } queue < int > q ; vector < int > visited ( n , 0 ) ; q . push ( 0 ) ; int ans = 0 ; while ( ! q . empty ( ) ) { int curr = q . front ( ) ; visited [ curr ] = 1 ; int count = 0 ; q . pop ( ) ; for ( int i = 0 ; i < graph_rev [ curr ] . size ( ) ; i ++ ) { if ( ! visited [ graph_rev [ curr ] [ i ] ] ) { q . push ( graph_rev [ curr ] [ i ] ) ; } } for ( int i = 0 ; i < graph [ curr ] . size ( ) ; i ++ ) { if ( ! visited [ graph [ curr ] [ i ] ] ) { q . push ( graph [ curr ] [ i ] ) ; count ++ ; } } ans += count ; } return ans ; } int main ( ) { vector < vector < int > > edges ; edges = { { 0 , 1 } , { 1 , 3 } , { 2 , 3 } , { 4 , 0 } , { 4 , 5 } } ; int n = 6 ; cout << minRev ( edges , n ) ; return 0 ; }