Given an array arr[0..n-1] of positive and negative numbers we need to find if there is a cycle in array with given rules of movements. If a number at an i index is positive, then move arr[i]%n forward steps, i.e., next index to visit is (i + arr[i])%n. Conversely, if it’s negative, move backward arr[i]%n steps i.e., next index to visit is (i – arr[i])%n. Here n is size of array. If value of arr[i]%n is zero, then it means no move from index i.

**Examples:**

Input: arr[] = {2, -1, 1, 2, 2} Output: Yes Explanation: There is a loop in this array because 0 moves to 2, 2 moves to 3, and 3 moves to 0. Input : arr[] = {1, 1, 1, 1, 1, 1} Output : Yes Whole array forms a loop. Input : arr[] = {1, 2} Output : No We move from 0 to index 1. From index 1, there is no move as 2%n is 0. Note that n is 2.

Note that self loops are not considered a cycle. For example {0} is not cyclic.

The idea is to form a directed graph of array elements using given set of rules. While forming the graph we don’t make self loops as value arr[i]%n equals to 0 means no moves. Finally our task reduces to detecting cycle in a directed graph. For detecting cycle, we use DFS and in DFS if reach a node which is visited and recursion call stack, we say there is a cycle.

## C++

`// C++ program to check if a given array is cyclic or not ` `#include<bits/stdc++.h> ` `using` `namespace` `std; ` ` ` `// 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. ` `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` `; ` ` ` `} ` ` ` ` ` `// There is a cycle if an adjacent is visited ` ` ` `// and present in recursion call stack recur[] ` ` ` `else` `if` `(visited[adj[v][i]] == ` `true` `&& ` ` ` `recur[adj[v][i]] == ` `true` `) ` ` ` `return` `true` `; ` ` ` `} ` ` ` ` ` `recur[v] = ` `false` `; ` ` ` `return` `false` `; ` `} ` ` ` `// Returns true if arr[] has cycle ` `bool` `isCycle(` `int` `arr[], ` `int` `n) ` `{ ` ` ` `// Create a graph using given moves in arr[] ` ` ` `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); ` ` ` ` ` `// Do DFS traversal of graph to detect cycle ` ` ` `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` `; ` `} ` ` ` `// Driver code ` `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; ` `} ` |

## Python3

# Python3 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/

def isCycleRec(v, adj, visited, recur):

visited[v] = True

recur[v] = True

for i in range(len(adj[v])):

if (visited[adj[v][i]] == False):

if (isCycleRec(adj[v][i], adj,

visited, recur)):

return True

# There is a cycle if an adjacent is visited

# and present in recursion call stack recur[]

elif (visited[adj[v][i]] == True and

recur[adj[v][i]] == True):

return True

recur[v] = False

return False

# Returns true if arr[] has cycle

def isCycle(arr, n):

# Create a graph using given

# moves in arr[]

adj = [[] for i in range(n)]

for i in range(n):

if (i != (i + arr[i] + n) % n):

adj[i].append((i + arr[i] + n) % n)

# Do DFS traversal of graph

# to detect cycle

visited = [False] * n

recur = [False] * n

for i in range(n):

if (visited[i] == False):

if (isCycleRec(i, adj,

visited, recur)):

return True

return True

# Driver code

if __name__ == ‘__main__’:

arr = [2, -1, 1, 2, 2]

n = len(arr)

if (isCycle(arr, n)):

print(“Yes”)

else:

print(“No”)

# This code is contributed by PranchalK

**Output :**

Yes

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

## leave a comment

## 0 Comments