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.

```
/* 
```

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

```
 */
```
```
#include<iostream>
```
```
#define SIZE 20
```
```
using namespace std;
```
```
 
```
```
bool map[SIZE][SIZE], F;
```
```
long long f[1 << SIZE][SIZE], res = 0;
```
```
/* 
```

 * Main: count the number of cycles in a graph

```
 */
```
```
int main()
```
```
{
```
```
    int n , m, i, j, k, l, x, y;
```
```
    cout<<"Enter number of vertices: ";
```
```
    cin>>n;
```
```
    cout<<"Enter number of edges: ";
```
```
    cin>>m;
```
```
    for (i = 0; i < m; i++)
```
```
    {
```

        cout<<"Enter source vertex of an edge: ";

```
        cin>>x;
```

        cout<<"Enter destination vertex of an edge: ";

```
        cin>>y;
```
```
        x--;
```
```
        y--;
```
```
        if (x > y)
```
```
           swap(x, y);
```
```
        map[x][y] = map[y][x] = 1;
```
```
        f[(1 << x) + (1 << y)][y] = 1;
```
```
    }
```
```
 
```
```
    for (i = 7; i < (1 << n); i++)
```
```
    {
```
```
        F = 1;
```
```
        for (j = 0; j < n; j++)
```
```
        {
```

            if (i & (1 << j) && f[i][j] == 0)

```
            {
```
```
                if (F)
```
```
                {
```
```
                    F = 0;
```
```
                    k = j;
```
```
                    continue;
```
```
                }
```

                for (l = k + 1; l < n; l++)

```
                {
```

                    if (i & (1 << l) && map[j][l])

                        f[i][j] += f[i - (1 << j)][l];

```
                }
```
```
                if (map[k][j])
```
```
                    res += f[i][j];
```
```
            }    
```
```
        }
```
```
    }
```

    cout<<"Number of Cycles: "<<res/2<<endl;

```
    return 0;
```
```
}
```

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

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

If you find any mistake above, kindly email to [email protected]

« Prev - C++ Program to Check Cycle in a Graph using Graph Traversal

» Next - C++ Program to Find Strongly Connected Components in Graphs

Related Posts:

Practice Computer Science MCQs
Practice Programming MCQs
Check Computer Science Books
Check Data Structure Books
Practice Design & Analysis of Algorithms MCQ

Recommended Articles: