C++ Program to Find Number of Cycles in a Graph

This C++ Program Finds the Number of Cycles in a Graph.

Here is source code of the C++ Program to Find Number of Cycles in a Graph. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

1. `/* `
2. ` * C++ Program to Find Number of Cycles in a Graph`
3. ` */`
4. `#include<iostream>`
5. `#define SIZE 20`
6. `using namespace std;`
7. ` `
8. `bool map[SIZE][SIZE], F;`
9. `long long f[1 << SIZE][SIZE], res = 0;`
10. `/* `
11. ` * Main: count the number of cycles in a graph`
12. ` */`
13. `int main()`
14. `{`
15. `    int n , m, i, j, k, l, x, y;`
16. `    cout<<"Enter number of vertices: ";`
17. `    cin>>n;`
18. `    cout<<"Enter number of edges: ";`
19. `    cin>>m;`
20. `    for (i = 0; i < m; i++)`
21. `    {`
22. `        cout<<"Enter source vertex of an edge: ";`
23. `        cin>>x;`
24. `        cout<<"Enter destination vertex of an edge: ";`
25. `        cin>>y;`
26. `        x--;`
27. `        y--;`
28. `        if (x > y)`
29. `           swap(x, y);`
30. `        map[x][y] = map[y][x] = 1;`
31. `        f[(1 << x) + (1 << y)][y] = 1;`
32. `    }`
33. ` `
34. `    for (i = 7; i < (1 << n); i++)`
35. `    {`
36. `        F = 1;`
37. `        for (j = 0; j < n; j++)`
38. `        {`
39. `            if (i & (1 << j) && f[i][j] == 0)`
40. `            {`
41. `                if (F)`
42. `                {`
43. `                    F = 0;`
44. `                    k = j;`
45. `                    continue;`
46. `                }`
47. `                for (l = k + 1; l < n; l++)`
48. `                {`
49. `                    if (i & (1 << l) && map[j][l])`
50. `                        f[i][j] += f[i - (1 << j)][l];`
51. `                }`
52. `                if (map[k][j])`
53. `                    res += f[i][j];`
54. `            }    `
55. `        }`
56. `    }`
57. `    cout<<"Number of Cycles: "<<res/2<<endl;`
58. `    return 0;`
59. `}`

```\$ g++ cycles_graph.cpp
\$ a.out

Enter number of vertices: 5
Enter number of edges: 8
Enter source vertex of an edge: 1
Enter destination vertex of an edge: 2
Enter source vertex of an edge: 1
Enter destination vertex of an edge: 5
Enter source vertex of an edge: 2
Enter destination vertex of an edge: 4
Enter source vertex of an edge: 2
Enter destination vertex of an edge: 3
Enter source vertex of an edge: 3
Enter destination vertex of an edge: 1
Enter source vertex of an edge: 4
Enter destination vertex of an edge: 3
Enter source vertex of an edge: 5
Enter destination vertex of an edge: 2
Enter source vertex of an edge: 5
Enter destination vertex of an edge: 1
Number of Cycles: 6

------------------
(program exited with code: 1)

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.