Count of elements which form a loop in an Array according to given constraints | Python3 program to number of elements which form a cycle in an array ; Function to count number of elements forming a cycle ; Array to store parent node of traversal . ; Array to determine whether current node is already counted in the cycle . ; Check if current node is already traversed or not . If node is not traversed yet then parent value will be - 1. ; Traverse the graph until an already visited node is not found . ; Check parent value to ensure a cycle is present . ; Count number of nodes in the cycle . ; Driver code
import math NEW_LINE mod = 1000000007 NEW_LINE def solve ( A , n ) : NEW_LINE INDENT cnt = 0 NEW_LINE parent = [ - 1 ] * n NEW_LINE vis = [ 0 ] * n NEW_LINE for i in range ( n ) : NEW_LINE INDENT j = i NEW_LINE if ( parent [ j ] == - 1 ) : NEW_LINE INDENT while ( parent [ j ] == - 1 ) : NEW_LINE INDENT parent [ j ] = i NEW_LINE j = math . gcd ( j , A [ j ] ) % n NEW_LINE DEDENT if ( parent [ j ] == i ) : NEW_LINE INDENT while ( vis [ j ] == 0 ) : NEW_LINE INDENT vis [ j ] = 1 NEW_LINE cnt += 1 NEW_LINE j = math . gcd ( j , A [ j ] ) % n NEW_LINE DEDENT DEDENT DEDENT DEDENT return cnt NEW_LINE DEDENT A = [ 1 , 1 , 6 , 2 ] NEW_LINE n = len ( A ) NEW_LINE print ( solve ( A , n ) ) NEW_LINE