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. }

advertisement
$ 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)
Press return to continue

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

advertisement
advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.