Find if an array of strings can be chained to form a circle | Set 2 | C ++ code to check if cyclic order is possible among strings under given constrainsts ; Utility method for a depth first search among vertices ; Returns true if all vertices are strongly connected i . e . can be made as loop ; Initialize all vertices as not visited ; perform a dfs from s ; now loop through all characters ; I character is marked ( i . e . it was first or last character of some string ) then it should be visited in last dfs ( as for looping , graph should be strongly connected ) ; If we reach that means graph is connected ; return true if an order among strings is possible ; Create an empty graph ; Initialize all vertices as not marked ; Initialize indegree and outdegree of every vertex as 0. ; Process all strings one by one ; Find first and last characters ; Mark the characters ; increase indegree and outdegree count ; Add an edge in graph ; If for any character indegree is not equal to outdegree then ordering is not possible ; Driver code to test above methods
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define M  26 NEW_LINE void dfs ( vector < int > g [ ] , int u , vector < bool > & visit ) { visit [ u ] = true ; for ( int i = 0 ; i < g [ u ] . size ( ) ; ++ i ) if ( ! visit [ g [ u ] [ i ] ] ) dfs ( g , g [ u ] [ i ] , visit ) ; } bool isConnected ( vector < int > g [ ] , vector < bool > & mark , int s ) { vector < bool > visit ( M , false ) ; dfs ( g , s , visit ) ; for ( int i = 0 ; i < M ; i ++ ) { if ( mark [ i ] && ! visit [ i ] ) return false ; } return true ; } bool possibleOrderAmongString ( string arr [ ] , int N ) { vector < int > g [ M ] ; vector < bool > mark ( M , false ) ; vector < int > in ( M , 0 ) , out ( M , 0 ) ; for ( int i = 0 ; i < N ; i ++ ) { int f = arr [ i ] . front ( ) - ' a ' ; int l = arr [ i ] . back ( ) - ' a ' ; mark [ f ] = mark [ l ] = true ; in [ l ] ++ ; out [ f ] ++ ; g [ f ] . push_back ( l ) ; } for ( int i = 0 ; i < M ; i ++ ) if ( in [ i ] != out [ i ] ) return false ; return isConnected ( g , mark , arr [ 0 ] . front ( ) - ' a ' ) ; } int main ( ) { string arr [ ] = { " ab " , " bc " , " cd " , " de " , " ed " , " da " } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; if ( possibleOrderAmongString ( arr , N ) == false ) cout << " Ordering ▁ not ▁ possible STRNEWLINE " ; else cout << " Ordering ▁ is ▁ possible STRNEWLINE " ; return 0 ; }