Check loop in array according to given constraints | C ++ program to check if a given array is cyclic or not ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool isCycleRec ( int v , vector < int > adj [ ] , vector < bool > & visited , vector < bool > & recur ) { visited [ v ] = true ; recur [ v ] = true ; for ( int i = 0 ; i < adj [ v ] . size ( ) ; i ++ ) { if ( visited [ adj [ v ] [ i ] ] == false ) { if ( isCycleRec ( adj [ v ] [ i ] , adj , visited , recur ) ) return true ; } else if ( visited [ adj [ v ] [ i ] ] == true && recur [ adj [ v ] [ i ] ] == true ) return true ; } recur [ v ] = false ; return false ; } bool isCycle ( int arr [ ] , int n ) { vector < int > adj [ n ] ; for ( int i = 0 ; i < n ; i ++ ) if ( i != ( i + arr [ i ] + n ) % n ) adj [ i ] . push_back ( ( i + arr [ i ] + n ) % n ) ; vector < bool > visited ( n , false ) ; vector < bool > recur ( n , false ) ; for ( int i = 0 ; i < n ; i ++ ) if ( visited [ i ] == false ) if ( isCycleRec ( i , adj , visited , recur ) ) return true ; return true ; } int main ( void ) { int arr [ ] = { 2 , -1 , 1 , 2 , 2 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; if ( isCycle ( arr , n ) ) cout << " Yes " << endl ; else cout << " No " << endl ; return 0 ; }