Find if an array of strings can be chained to form a circle | Set 2 | Python3 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
M = 26 NEW_LINE def dfs ( g , u , visit ) : NEW_LINE INDENT visit [ u ] = True NEW_LINE for i in range ( len ( g [ u ] ) ) : NEW_LINE INDENT if ( not visit [ g [ u ] [ i ] ] ) : NEW_LINE INDENT dfs ( g , g [ u ] [ i ] , visit ) NEW_LINE DEDENT DEDENT DEDENT def isConnected ( g , mark , s ) : NEW_LINE INDENT visit = [ False for i in range ( M ) ] NEW_LINE dfs ( g , s , visit ) NEW_LINE for i in range ( M ) : NEW_LINE INDENT if ( mark [ i ] and ( not visit [ i ] ) ) : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT return True NEW_LINE DEDENT def possibleOrderAmongString ( arr , N ) : NEW_LINE INDENT g = { } NEW_LINE mark = [ False for i in range ( M ) ] NEW_LINE In = [ 0 for i in range ( M ) ] NEW_LINE out = [ 0 for i in range ( M ) ] NEW_LINE for i in range ( N ) : NEW_LINE INDENT f = ( ord ( arr [ i ] [ 0 ] ) - ord ( ' a ' ) ) NEW_LINE l = ( ord ( arr [ i ] [ - 1 ] ) - ord ( ' a ' ) ) NEW_LINE mark [ f ] = True NEW_LINE mark [ l ] = True NEW_LINE In [ l ] += 1 NEW_LINE out [ f ] += 1 NEW_LINE if f not in g : NEW_LINE INDENT g [ f ] = [ ] NEW_LINE DEDENT g [ f ] . append ( l ) NEW_LINE DEDENT for i in range ( M ) : NEW_LINE INDENT if ( In [ i ] != out [ i ] ) : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT return isConnected ( g , mark , ord ( arr [ 0 ] [ 0 ] ) - ord ( ' a ' ) ) NEW_LINE DEDENT arr = [ " ab " , " bc " , " cd " , " de " , " ed " , " da " ] NEW_LINE N = len ( arr ) NEW_LINE if ( possibleOrderAmongString ( arr , N ) == False ) : NEW_LINE INDENT print ( " Ordering ▁ not ▁ possible " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " Ordering ▁ is ▁ possible " ) NEW_LINE DEDENT