Cycles of length n in an undirected and connected graph | CPP Program to count cycles of length n in a given graph . ; Number of vertices ; mark the vertex vert as visited ; if the path of length ( n - 1 ) is found ; mark vert as un - visited to make it usable again . ; Check if vertex vert can end with vertex start ; For searching every possible path of length ( n - 1 ) ; DFS for searching path by decreasing length by 1 ; marking vert as unvisited to make it usable again . ; Counts cycles of length N in an undirected and connected graph . ; all vertex are marked un - visited initially . ; Searching for cycle by using v - n + 1 vertices ; ith vertex is marked as visited and will not be visited again . ; driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int V = 5 ; void DFS ( bool graph [ ] [ V ] , bool marked [ ] , int n , int vert , int start , int & count ) { marked [ vert ] = true ; if ( n == 0 ) { marked [ vert ] = false ; if ( graph [ vert ] [ start ] ) { count ++ ; return ; } else return ; } for ( int i = 0 ; i < V ; i ++ ) if ( ! marked [ i ] && graph [ vert ] [ i ] ) DFS ( graph , marked , n - 1 , i , start , count ) ; marked [ vert ] = false ; } int countCycles ( bool graph [ ] [ V ] , int n ) { bool marked [ V ] ; memset ( marked , 0 , sizeof ( marked ) ) ; int count = 0 ; for ( int i = 0 ; i < V - ( n - 1 ) ; i ++ ) { DFS ( graph , marked , n - 1 , i , i , count ) ; marked [ i ] = true ; } return count / 2 ; } int main ( ) { bool graph [ ] [ V ] = { { 0 , 1 , 0 , 1 , 0 } , { 1 , 0 , 1 , 0 , 1 } , { 0 , 1 , 0 , 1 , 0 } , { 1 , 0 , 1 , 0 , 1 } , { 0 , 1 , 0 , 1 , 0 } } ; int n = 4 ; cout << " Total ▁ cycles ▁ of ▁ length ▁ " << n << " ▁ are ▁ " << countCycles ( graph , n ) ; return 0 ; }