Cycles of length n in an undirected and connected 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 . ; main :
V = 5 NEW_LINE def DFS ( graph , marked , n , vert , start , count ) : NEW_LINE INDENT marked [ vert ] = True NEW_LINE if n == 0 : NEW_LINE INDENT marked [ vert ] = False NEW_LINE if graph [ vert ] [ start ] == 1 : NEW_LINE INDENT count = count + 1 NEW_LINE return count NEW_LINE DEDENT else : NEW_LINE INDENT return count NEW_LINE DEDENT DEDENT for i in range ( V ) : NEW_LINE INDENT if marked [ i ] == False and graph [ vert ] [ i ] == 1 : NEW_LINE INDENT count = DFS ( graph , marked , n - 1 , i , start , count ) NEW_LINE DEDENT DEDENT marked [ vert ] = False NEW_LINE return count NEW_LINE DEDENT def countCycles ( graph , n ) : NEW_LINE INDENT marked = [ False ] * V NEW_LINE count = 0 NEW_LINE for i in range ( V - ( n - 1 ) ) : NEW_LINE INDENT count = DFS ( graph , marked , n - 1 , i , i , count ) NEW_LINE marked [ i ] = True NEW_LINE DEDENT return int ( count / 2 ) NEW_LINE DEDENT graph = [ [ 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 ] ] NEW_LINE n = 4 NEW_LINE print ( " Total ▁ cycles ▁ of ▁ length ▁ " , n , " ▁ are ▁ " , countCycles ( graph , n ) ) NEW_LINE