Count of elements which form a loop in an Array according to given constraints | C ++ 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 . ; Initialize the arrays . ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define mp  make_pair NEW_LINE #define pb  push_back NEW_LINE #define mod  1000000007 NEW_LINE int solve ( int A [ ] , int n ) { int i , cnt = 0 , j ; int parent [ n ] ; int vis [ n ] ; memset ( parent , -1 , sizeof ( parent ) ) ; memset ( vis , 0 , sizeof ( vis ) ) ; for ( i = 0 ; i < n ; i ++ ) { j = i ; if ( parent [ j ] == -1 ) { while ( parent [ j ] == -1 ) { parent [ j ] = i ; j = __gcd ( j , A [ j ] ) % n ; } if ( parent [ j ] == i ) { while ( ! vis [ j ] ) { vis [ j ] = 1 ; cnt ++ ; j = __gcd ( j , A [ j ] ) % n ; } } } } return cnt ; } int main ( ) { int A [ ] = { 1 , 1 , 6 , 2 } ; int n = sizeof ( A ) / sizeof ( A [ 0 ] ) ; cout << solve ( A , n ) ; return 0 ; }