Convert undirected connected graph to strongly connected directed graph | C ++ program for the above approach ; To store the assigned Edges ; Flag variable to check Bridges ; Function to implement DFS Traversal ; Mark the current node as visited ; Update the order of node v ; Update the bridge_detect for node v ; Traverse the adjacency list of Node v ; Ignores if same edge is traversed ; Ignores the edge u -- > v as v -- > u is already processed ; Finds a back Edges , cycle present ; Update the bridge_detect [ v ] ; Else DFS traversal for current node in the adjacency list ; Update the bridge_detect [ v ] ; Store the current directed Edge ; Condition for Bridges ; Return flag ; Function to print the direction of edges to make graph SCCs ; Arrays to store the visited , bridge_detect and order of Nodes ; DFS Traversal from vertex 1 ; If flag is zero , then Bridge is present in the graph ; Else print the direction of Edges assigned ; Function to create graph ; Traverse the Edges ; Push the edges in an adjacency list ; Driver Code ; N vertices and M Edges ; To create Adjacency List ; Create an undirected graph ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; vector < pair < int , int > > ans ; int flag = 1 ; int dfs ( vector < int > adj [ ] , int * order , int * bridge_detect , bool * mark , int v , int l ) { mark [ v ] = 1 ; order [ v ] = order [ l ] + 1 ; bridge_detect [ v ] = order [ v ] ; for ( int i = 0 ; i < adj [ v ] . size ( ) ; i ++ ) { int u = adj [ v ] [ i ] ; if ( u == l ) { continue ; } if ( order [ v ] < order [ u ] ) { continue ; } if ( mark [ u ] ) { bridge_detect [ v ] = min ( order [ u ] , bridge_detect [ v ] ) ; } else { dfs ( adj , order , bridge_detect , mark , u , v ) ; } bridge_detect [ v ] = min ( bridge_detect [ u ] , bridge_detect [ v ] ) ; ans . push_back ( make_pair ( v , u ) ) ; } if ( bridge_detect [ v ] == order [ v ] && l != 0 ) { flag = 0 ; } return flag ; } void convert ( vector < int > adj [ ] , int n ) { int order [ n ] = { 0 } ; int bridge_detect [ n ] = { 0 } ; bool mark [ n ] ; memset ( mark , false , sizeof ( mark ) ) ; int flag = dfs ( adj , order , bridge_detect , mark , 1 , 0 ) ; if ( flag == 0 ) { cout << " - 1" ; } else { for ( auto & it : ans ) { cout << it . first << " - > " << it . second << ' ' ; } } } void createGraph ( int Edges [ ] [ 2 ] , vector < int > adj [ ] , int M ) { for ( int i = 0 ; i < M ; i ++ ) { int u = Edges [ i ] [ 0 ] ; int v = Edges [ i ] [ 1 ] ; adj [ u ] . push_back ( v ) ; adj [ v ] . push_back ( u ) ; } } int main ( ) { int N = 5 , M = 6 ; int Edges [ M ] [ 2 ] = { { 0 , 1 } , { 0 , 2 } , { 1 , 2 } , { 1 , 4 } , { 2 , 3 } , { 3 , 4 } } ; vector < int > adj [ N ] ; createGraph ( Edges , adj , M ) ; convert ( adj , N ) ; return 0 ; }