Tutorialspoint.dev

Check loop in array according to given constraints

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.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter