# Cycles of length n in an undirected and connected graph

Given an undirected and connected graph and a number n, count total number of cycles of length n in the graph. A cycle of length n simply means that the cycle contains n vertices and n edges. And we have to count all such cycles that exist.
Example :

```Input :  n = 4

Output : Total cycles = 3
Explanation : Following 3 unique cycles
0 -> 1 -> 2 -> 3 -> 0
0 -> 1 -> 4 -> 3 -> 0
1 -> 2 -> 3 -> 4 -> 1
Note* : There are more cycles but
these 3 are unique as 0 -> 3 -> 2 -> 1
-> 0 and 0 -> 1 -> 2 -> 3 -> 0 are
same cycles and hence will be counted as 1.
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

To solve this Problem, DFS(Depth First Search) can be effectively used. Using DFS we find every possible path of length (n-1) for a particular source (or starting point). Then we check if this path ends with the vertex it started with, if yes then we count this as the cycle of length n. Notice that we looked for path of length (n-1) because the nth edge will be the closing edge of cycle.

Every possible path of length (n-1) can be searched using only V – (n1) vertices (where V is the total number of vertices).
For above example, all the cycles of length 4 can be searched using only 5-(4-1) = 2 vertices. The reason behind this is quite simple, because we search for all possible path of length (n-1) = 3 using these 2 vertices which include the remaining 3 vertices. So, these 2 vertices cover the cycles of remaining 3 vertices as well, and using only 3 vertices we can’t form a cycle of length 4 anyways.

One more thing to notice is that, every vertex finds 2 duplicate cycles for every cycle that it forms. For above example 0th vertex finds two duplicate cycle namely 0 -> 3 -> 2 -> 1 -> 0 and 0 -> 1 -> 2 -> 3 -> 0. Hence the total count must be divided by 2 because every cycle is counted twice.

## C++

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

## Java

 `// Java program to calculate cycles of ` `// length n in a given graph ` `public` `class` `Main { ` `     `  `    ``// Number of vertices ` `    ``public` `static` `final` `int` `V = ``5``; ` `    ``static` `int` `count = ``0``; ` `     `  `    ``static` `void` `DFS(``int` `graph[][], ``boolean` `marked[], ` `                    ``int` `n, ``int` `vert, ``int` `start) { ` `         `  `        ``// mark the vertex vert as visited ` `        ``marked[vert] = ``true``; ` `         `  `        ``// if the path of length (n-1) is found ` `        ``if` `(n == ``0``) { ` `             `  `            ``// mark vert as un-visited to  ` `            ``// make it usable again ` `            ``marked[vert] = ``false``; ` `             `  `            ``// Check if vertex vert end  ` `            ``// with vertex start ` `            ``if` `(graph[vert][start] == ``1``) { ` `                ``count++; ` `                ``return``; ` `            ``} ``else` `                ``return``; ` `        ``} ` `         `  `        ``// For searching every possible  ` `        ``// path of length (n-1) ` `        ``for` `(``int` `i = ``0``; i < V; i++) ` `            ``if` `(!marked[i] && graph[vert][i] == ``1``) ` `             `  `                ``// DFS for searching path by ` `                ``// decreasing length by 1 ` `                ``DFS(graph, marked, n-``1``, i, start); ` `         `  `        ``// marking vert as unvisited to make it ` `        ``// usable again ` `        ``marked[vert] = ``false``; ` `    ``} ` `     `  `    ``// Count cycles of length N in an  ` `    ``// undirected and connected graph. ` `    ``static` `int` `countCycles(``int` `graph[][], ``int` `n) { ` `         `  `        ``// all vertex are marked un-visited ` `        ``// initially. ` `        ``boolean` `marked[] = ``new` `boolean``[V]; ` `         `  `        ``// Searching for cycle by using  ` `        ``// v-n+1 vertices ` `        ``for` `(``int` `i = ``0``; i < V - (n - ``1``); i++) { ` `            ``DFS(graph, marked, n-``1``, i, i); ` `             `  `            ``// ith vertex is marked as visited ` `            ``// and will not be visited again ` `            ``marked[i] = ``true``; ` `        ``} ` `         `  `        ``return` `count / ``2``;  ` `    ``} ` `     `  `    ``// driver code ` `    ``public` `static` `void` `main(String[] args) { ` `        ``int` `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``}}; ` `         `  `        ``int` `n = ``4``; ` `         `  `        ``System.out.println(``"Total cycles of length "``+ ` `                          ``n + ``" are "``+  ` `                          ``countCycles(graph, n)); ` `    ``} ` `} ` ` `  `// This code is contributed by nuclode `

## Python3

 `# Python Program to count ` `# cycles of length n ` `# in a given graph. ` `  `  `# Number of vertices ` `V ``=` `5` ` `  `def` `DFS(graph, marked, n, vert, start, count): ` ` `  `    ``# mark the vertex vert as visited ` `    ``marked[vert] ``=` `True` `  `  `    ``# if the path of length (n-1) is found ` `    ``if` `n ``=``=` `0``:  ` ` `  `        ``# mark vert as un-visited to make ` `        ``# it usable again. ` `        ``marked[vert] ``=` `False` `  `  `        ``# Check if vertex vert can end with ` `        ``# vertex start ` `        ``if` `graph[vert][start] ``=``=` `1``: ` `            ``count ``=` `count ``+` `1` `            ``return` `count ` `        ``else``: ` `            ``return` `count ` `  `  `    ``# For searching every possible path of ` `    ``# length (n-1) ` `    ``for` `i ``in` `range``(V): ` `        ``if` `marked[i] ``=``=` `False` `and` `graph[vert][i] ``=``=` `1``: ` ` `  `            ``# DFS for searching path by decreasing ` `            ``# length by 1 ` `            ``count ``=` `DFS(graph, marked, n``-``1``, i, start, count) ` `  `  `    ``# marking vert as unvisited to make it ` `    ``# usable again. ` `    ``marked[vert] ``=` `False` `    ``return` `count ` `  `  `# Counts cycles of length ` `# N in an undirected ` `# and connected graph. ` `def` `countCycles( graph, n): ` ` `  `    ``# all vertex are marked un-visited intially. ` `    ``marked ``=` `[``False``] ``*` `V  ` `  `  `    ``# Searching for cycle by using v-n+1 vertices ` `    ``count ``=` `0` `    ``for` `i ``in` `range``(V``-``(n``-``1``)): ` `        ``count ``=` `DFS(graph, marked, n``-``1``, i, i, count) ` `  `  `        ``# ith vertex is marked as visited and ` `        ``# will not be visited again. ` `        ``marked[i] ``=` `True` `     `  `    ``return` `int``(count``/``2``) ` `  `  `# main : ` `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``]] ` `           `  `n ``=` `4` `print``(``"Total cycles of length "``,n,``" are "``,countCycles(graph, n)) ` ` `  `# this code is contributed by Shivani Ghughtyal `

## C#

 `// C# program to calculate cycles of ` `// length n in a given graph ` `using` `System; ` ` `  `class` `GFG  ` `{ ` `     `  `    ``// Number of vertices ` `    ``public` `static` `int` `V = 5; ` `    ``static` `int` `count = 0; ` `     `  `    ``static` `void` `DFS(``int` `[,]graph, ``bool` `[]marked, ` `                    ``int` `n, ``int` `vert, ``int` `start)  ` `    ``{ ` `         `  `        ``// mark the vertex vert as visited ` `        ``marked[vert] = ``true``; ` `         `  `        ``// if the path of length (n-1) is found ` `        ``if` `(n == 0)  ` `        ``{ ` `             `  `            ``// mark vert as un-visited to  ` `            ``// make it usable again ` `            ``marked[vert] = ``false``; ` `             `  `            ``// Check if vertex vert end  ` `            ``// with vertex start ` `            ``if` `(graph[vert, start] == 1) ` `            ``{ ` `                ``count++; ` `                ``return``; ` `            ``}  ` `            ``else` `                ``return``; ` `        ``} ` `         `  `        ``// For searching every possible  ` `        ``// path of length (n-1) ` `        ``for` `(``int` `i = 0; i < V; i++) ` `            ``if` `(!marked[i] && graph[vert, i] == 1) ` `             `  `                ``// DFS for searching path by ` `                ``// decreasing length by 1 ` `                ``DFS(graph, marked, n - 1, i, start); ` `         `  `        ``// marking vert as unvisited to make it ` `        ``// usable again ` `        ``marked[vert] = ``false``; ` `    ``} ` `     `  `    ``// Count cycles of length N in an  ` `    ``// undirected and connected graph. ` `    ``static` `int` `countCycles(``int` `[,]graph, ``int` `n)  ` `    ``{ ` `         `  `        ``// all vertex are marked un-visited ` `        ``// initially. ` `        ``bool` `[]marked = ``new` `bool``[V]; ` `         `  `        ``// Searching for cycle by using  ` `        ``// v-n+1 vertices ` `        ``for` `(``int` `i = 0; i < V - (n - 1); i++)  ` `        ``{ ` `            ``DFS(graph, marked, n - 1, i, i); ` `             `  `            ``// ith vertex is marked as visited ` `            ``// and will not be visited again ` `            ``marked[i] = ``true``; ` `        ``} ` `         `  `        ``return` `count / 2;  ` `    ``} ` `     `  `    ``// Driver code ` `    ``public` `static` `void` `Main() ` `    ``{ ` `        ``int` `[,]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}}; ` `         `  `        ``int` `n = 4; ` `         `  `        ``Console.WriteLine(``"Total cycles of length "``+ ` `                        ``n + ``" are "``+  ` `                        ``countCycles(graph, n)); ` `    ``} ` `} ` ` `  `/* This code contributed by PrinciRaj1992 */`

Output:

```Total cycles of length 4 are 3
```

## tags:

Graph graph-connectivity graph-cycle Graph