Check loop in array according to given constraints | A simple Graph DFS based recursive function to check if there is cycle in graph with vertex v as root of DFS . Refer below article for details . https : www . geeksforgeeks . org / detect - cycle - in - a - graph / ; There is a cycle if an adjacent is visited and present in recursion call stack recur [ ] ; Returns true if arr [ ] has cycle ; Create a graph using given moves in arr [ ] ; Do DFS traversal of graph to detect cycle ; Driver code
def isCycleRec ( v , adj , visited , recur ) : NEW_LINE INDENT visited [ v ] = True NEW_LINE recur [ v ] = True NEW_LINE for i in range ( len ( adj [ v ] ) ) : NEW_LINE INDENT if ( visited [ adj [ v ] [ i ] ] == False ) : NEW_LINE INDENT if ( isCycleRec ( adj [ v ] [ i ] , adj , visited , recur ) ) : NEW_LINE INDENT return True NEW_LINE DEDENT DEDENT elif ( visited [ adj [ v ] [ i ] ] == True and recur [ adj [ v ] [ i ] ] == True ) : NEW_LINE INDENT return True NEW_LINE DEDENT DEDENT recur [ v ] = False NEW_LINE return False NEW_LINE DEDENT def isCycle ( arr , n ) : NEW_LINE INDENT adj = [ [ ] for i in range ( n ) ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( i != ( i + arr [ i ] + n ) % n ) : NEW_LINE INDENT adj [ i ] . append ( ( i + arr [ i ] + n ) % n ) NEW_LINE DEDENT DEDENT visited = [ False ] * n NEW_LINE recur = [ False ] * n NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( visited [ i ] == False ) : NEW_LINE INDENT if ( isCycleRec ( i , adj , visited , recur ) ) : NEW_LINE INDENT return True NEW_LINE DEDENT DEDENT DEDENT return True NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 2 , - 1 , 1 , 2 , 2 ] NEW_LINE n = len ( arr ) NEW_LINE if ( isCycle ( arr , n ) ) : NEW_LINE INDENT print ( " Yes " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No " ) NEW_LINE DEDENT DEDENT