Count of simple cycles in an undirected graph having N vertices

19 June 2025

0

Given an undirected unweighted graph of N vertices in the form of adjacency matrix adj[][], the task is to find the number of simple cycles in it.

Input: adj[][] = { { 0, 1, 1, 1 }, { 1, 0, 1, 0 }, { 1, 1, 0, 1 }, { 1, 0, 1, 0 } }
Output: 2
Explanation: The graph is shown below as:

The given graph consists of two simple cycles as shown
Input: adj[][] = { { 0, 1, 1, 0 }, { 1, 0, 0, 1 }, { 1, 0, 0, 1 }, { 0, 1, 1, 0 } }
Output: 1

Approach: The given problem can be solved by using Dynamic Programming with Bitmasking, the dynamic programming state for the Hamiltonian paths is defined as the dp[mask][i] as the number of paths that cover the node-set mask and ends at i and iterate from 0 to N-1 and in each iteration, compute the number of loops containing the current node without the previous node and sum them up, Since there are two directions for a loop divide the result by 2. Follow the steps below to solve the problem:

Initialize a variable ans as 0 that stores the resultant count of cycles.
Initialize a 2-D array dp[][] array of dimensions 2^N and N and initialize it with 0.
Iterate over the range [0, 2^N – 1) using the variable mask and perform the following tasks:
- Initialize 2 variables nodeSet and firstSetBit as the number of set bits and the first set bit in mask.
- If nodeSet equals 1, then set the value of dp[mask][firstSetBit] as 1.
- Now, For each mask having set bits greater than 1, iterate over the range [firstSetBit + 1, N – 1) using the variable j and if the Bitwise AND of mask & 2^j is true, then initialize a variable newNodeSet as mask^2^j and iterate over the range [0, N) using the variable k and perform the following tasks:
  - Check if there is an edge between nodes k and j(k is not equal to j).
  - If there is an edge then add the number of loops in this mask that ends at k and does not contain j to the state for the node-set mask as follows dp[mask][j] = dp[mask][j]+ dp[mask XOR 2^j][k].
  - If adj[j][firstSetBit] is 1 and nodeSet is greater than 2, then add the value of dp[mask][j] to the variable ans.
After performing the above steps, print the value of ans as the answer.

Below is the implementation of the above approach.

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the number of simple
// cycles in an undirected unweighted graph
void findNumberOfSimpleCycles(
int N, vector<vector<int> > adj)
{
    // Stores the count of cycles
    int ans = 0;
    int dp[(1 << N)][N];
 
    // Initialize it with 0
    memset(dp, 0, sizeof dp);
 
    // Iterate over all subsets
    for (int mask = 0;
         mask < (1 << N); mask++) {
 
        // Find the number of set bits
        int nodeSet
            = __builtin_popcountll(mask);
 
        // Find the first set bit
        int firstSetBit
            = __builtin_ffsl(mask);
 
        // If the nodeSet contains only
        // 1 set bit
        if (nodeSet == 1) {
 
            // Initialize it with 1
            dp[mask][firstSetBit] = 1;
        }
        else {
 
            // Iterate over all bits
            // of the mask
            for (int j = firstSetBit + 1;
                 j < N; j++) {
 
                // Check if the  bit is set
                // and is not the first node
                if ((mask & (1 << j))) {
 
                    // Remove this bit and
                    // compute the node set
                    int newNodeSet = mask ^ (1 << j);
 
                    // Iterate over the masks
                    // not equal to j
                    for (int k = 0; k < N; k++) {
 
                        // If the kth bit is set &
                        // there is an edge from k to j
                        if ((newNodeSet & (1 << k))
                            && adj[k][j]) {
                            dp[mask][j]
                                += dp[newNodeSet][k];
 
                            // If the first node is
                            // connected with the jth
                            if (adj[j][firstSetBit]
                                && nodeSet > 2)
                                ans += dp[mask][j];
                        }
                    }
                }
            }
        }
    }
 
    // Print the answer
    cout << ans << endl;
}
 
// Driver Code
int main()
{
    // Given input graph in the form
    // of adjacency matrix
    vector<vector<int> > adj
        = { { 0, 1, 1, 1 },
            { 1, 0, 1, 0 },
            { 1, 1, 0, 1 },
            { 1, 0, 1, 0 } };
 
    // Number of vertices in the graph
    int N = adj.size();
 
    findNumberOfSimpleCycles(N, adj);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
    static int __builtin_popcountll(long x)
    {
        int setBits = 0;
        while (x != 0) {
            x = x & (x - 1);
            setBits++;
        }
        return setBits;
    }
    static int getFirstSetBitPos(int n)
    {
        return (int)((Math.log10(n & -n)) / Math.log10(2)) + 1;
    }
   
// Function to find the number of simple
// cycles in an undirected unweighted graph
static void findNumberOfSimpleCycles(
int N, int[][] adj)
{
   
    // Stores the count of cycles
    int ans = 1;
    int [][]dp = new int[(1 << N)][N];
 
    // Iterate over all subsets
    for (int mask = 0;
         mask < (1 << N); mask++) {
 
        // Find the number of set bits
        int nodeSet
            = __builtin_popcountll(mask);
 
        // Find the first set bit
        int firstSetBit
            = getFirstSetBitPos(mask);
 
        // If the nodeSet contains only
        // 1 set bit
        if (nodeSet == 1) {
 
            // Initialize it with 1
            dp[mask][firstSetBit-1] = 1;
        }
        else {
 
            // Iterate over all bits
            // of the mask
            for (int j = firstSetBit + 1;
                 j < N; j++) {
 
                // Check if the  bit is set
                // and is not the first node
                if ((mask & (1 << j))!=0) {
 
                    // Remove this bit and
                    // compute the node set
                    int newNodeSet = mask ^ (1 << j);
 
                    // Iterate over the masks
                    // not equal to j
                    for (int k = 0; k < N; k++) {
 
                        // If the kth bit is set &
                        // there is an edge from k to j
                        if ((newNodeSet & (1 << k)) !=0
                            && adj[k][j]  !=0) {
                            dp[mask][j]
                                += dp[newNodeSet][k];
 
                            // If the first node is
                            // connected with the jth
                            if (adj[j][firstSetBit]!=0
                                && nodeSet > 2)
                                ans += dp[mask][j];
                        }
                    }
                }
            }
        }
    }
 
    // Print the answer
    System.out.print(ans +"\n");
}
 
// Driver Code
public static void main(String[] args)
{
   
    // Given input graph in the form
    // of adjacency matrix
    int[][] adj
        = { { 0, 1, 1, 1 },
            { 1, 0, 1, 0 },
            { 1, 1, 0, 1 },
            { 1, 0, 1, 0 } };
 
    // Number of vertices in the graph
    int N = adj.length;
 
    findNumberOfSimpleCycles(N, adj);
 
}
}
 
// This code is contributed by umadevi9616 

Python3

# Python program for the above approach:
import math
 
# Function to count set bits in an integer 
# in Python 
def __builtin_popcountll(num):
     
    # convert given number into binary 
    # output will be like bin(11)=0b1101 
    binary = bin(num)
 
    # now separate out all 1's from binary string 
    # we need to skip starting two characters
    # of binary string i.e; 0b 
    setBits = [ones for ones in binary[2:] if ones=='1']
    return len(setBits)
 
##Function to find position
## of 1st set bit
def __builtin_ffsl(n):
    if n == 0:
        return 0
 
    return math.floor(math.log2(n & -n)) + 1
 
## Function to find the number of simple
## cycles in an undirected unweighted graph
def findNumberOfSimpleCycles(N, adj):
    ## Stores the count of cycles
    ans = 1
    dp = []
 
    for i in range(0, (1 << N)):
        dp.append([])
        for j in range(0, N):
 
            dp[i].append(0)
 
    for i in range(0, (1 << N)):
        for j in range(0, N):
            if(dp[i][j] != 0):
                print(dp[i][j], i, j)
 
    ## Iterate over all subsets
    for mask in range(0, (1 << N)):
 
        ## Find the number of set bits
        nodeSet = __builtin_popcountll(mask)
 
        ## Find the first set bit
        firstSetBit = __builtin_ffsl(mask)
 
        ## If the nodeSet contains only
        ## 1 set bit
        if (nodeSet == 1):
 
            ## Initialize it with 1
            dp[mask][firstSetBit-1] = 1
        else:
 
            ## Iterate over all bits
            ## of the mask
            for j in range(firstSetBit + 1, N):
 
                ## Check if the bit is set
                ## and is not the first node
                if (mask & (1 << j)) != 0:
 
                    ## Remove this bit and
                    ## compute the node set
                    newNodeSet = mask ^ (1 << j)
 
                    ## Iterate over the masks
                    ## not equal to j
                    for k in range(0, N):
 
                        ## If the kth bit is set &
                        ## there is an edge from k to j
                        if (((newNodeSet & (1 << k)) > 0) and adj[k][j] > 0):
                            dp[mask][j] += dp[newNodeSet][k]
 
                            ## If the first node is
                            ## connected with the jth
                            if ((adj[j][firstSetBit] > 0) and nodeSet > 2):
                                ans += dp[mask][j]
 
    ## Print the answer
    print(ans)
 
 
## Driver code
if __name__=='__main__':
 
    ## Given input graph in the form
    ## of adjacency matrix
    adj = [ [ 0, 1, 1, 1 ],
            [ 1, 0, 1, 0 ],
            [ 1, 1, 0, 1 ],
            [ 1, 0, 1, 0 ] ]
 
    ## Number of vertices in the graph
    N = len(adj)
 
    findNumberOfSimpleCycles(N, adj)
 
    # This code is contributed by subhamgoyal2014.

C#

// C# program for the above approach
using System;
 
public class GFG{
    static int __builtin_popcountll(long x)
    {
        int setBits = 0;
        while (x != 0) {
            x = x & (x - 1);
            setBits++;
        }
        return setBits;
    }
    static int getFirstSetBitPos(int n)
    {
        return (int)((Math.Log10(n & -n)) / Math.Log10(2)) + 1;
    }
   
// Function to find the number of simple
// cycles in an undirected unweighted graph
static void findNumberOfSimpleCycles(
int N, int[,] adj)
{
   
    // Stores the count of cycles
    int ans = 1;
    int [,]dp = new int[(1 << N),N];
 
    // Iterate over all subsets
    for (int mask = 0;
         mask < (1 << N); mask++) {
 
        // Find the number of set bits
        int nodeSet
            = __builtin_popcountll(mask);
 
        // Find the first set bit
        int firstSetBit
            = getFirstSetBitPos(mask);
 
        // If the nodeSet contains only
        // 1 set bit
        if (nodeSet == 1) {
 
            // Initialize it with 1
            dp[mask,firstSetBit-1] = 1;
        }
        else {
 
            // Iterate over all bits
            // of the mask
            for (int j = firstSetBit + 1;
                 j < N; j++) {
 
                // Check if the  bit is set
                // and is not the first node
                if ((mask & (1 << j))!=0) {
 
                    // Remove this bit and
                    // compute the node set
                    int newNodeSet = mask ^ (1 << j);
 
                    // Iterate over the masks
                    // not equal to j
                    for (int k = 0; k < N; k++) {
 
                        // If the kth bit is set &
                        // there is an edge from k to j
                        if ((newNodeSet & (1 << k)) !=0
                            && adj[k,j]  !=0) {
                            dp[mask,j]
                                += dp[newNodeSet,k];
 
                            // If the first node is
                            // connected with the jth
                            if (adj[j,firstSetBit]!=0
                                && nodeSet > 2)
                                ans += dp[mask,j];
                        }
                    }
                }
            }
        }
    }
 
    // Print the answer
    Console.Write(ans +"\n");
}
 
// Driver Code
public static void Main(String[] args)
{
   
    // Given input graph in the form
    // of adjacency matrix
    int[,] adj
        = { { 0, 1, 1, 1 },
            { 1, 0, 1, 0 },
            { 1, 1, 0, 1 },
            { 1, 0, 1, 0 } };
 
    // Number of vertices in the graph
    int N = adj.GetLength(0);
 
    findNumberOfSimpleCycles(N, adj);
 
}
}
 
// This code is contributed by gauravrajput1

Javascript

<script>
// javascript program for the above approach
   function __builtin_popcountll(x)
    {
        var setBits = 0;
        while (x != 0) {
            x = x & (x - 1);
            setBits++;
        }
        return setBits;
    }
    function getFirstSetBitPos(n)
    {
        return parseInt(((Math.log10(n & -n)) / Math.log10(2)) + 1);
    }
   
// Function to find the number of simple
// cycles in an undirected unweighted graph
function findNumberOfSimpleCycles(
 N,  adj)
{
   
    // Stores the count of cycles
    var ans = 1;
    var dp = Array(1 << N).fill().map(()=>Array(N).fill(0));
 
    // Iterate over all subsets
    for (var mask = 0;
         mask < (1 << N); mask++) {
 
        // Find the number of set bits
        var nodeSet
            = __builtin_popcountll(mask);
 
        // Find the first set bit
        var firstSetBit
            = getFirstSetBitPos(mask);
 
        // If the nodeSet contains only
        // 1 set bit
        if (nodeSet == 1) {
 
            // Initialize it with 1
            dp[mask][firstSetBit-1] = 1;
        }
        else {
 
            // Iterate over all bits
            // of the mask
            for (j = firstSetBit + 1;
                 j < N; j++) {
 
                // Check if the  bit is set
                // and is not the first node
                if ((mask & (1 << j))!=0) {
 
                    // Remove this bit and
                    // compute the node set
                    var newNodeSet = mask ^ (1 << j);
 
                    // Iterate over the masks
                    // not equal to j
                    for (k = 0; k < N; k++) {
 
                        // If the kth bit is set &
                        // there is an edge from k to j
                        if ((newNodeSet & (1 << k)) !=0
                            && adj[k][j]  !=0) {
                            dp[mask][j]
                                += dp[newNodeSet][k];
 
                            // If the first node is
                            // connected with the jth
                            if (adj[j][firstSetBit]!=0
                                && nodeSet > 2)
                                ans += dp[mask][j];
                        }
                    }
                }
            }
        }
    }
 
    // Print the answer
    document.write(ans +"\n");
}
 
// Driver Code
 
    // Given input graph in the form
    // of adjacency matrix
    var adj
        = [ [ 0, 1, 1, 1 ],
            [ 1, 0, 1, 0 ],
            [ 1, 1, 0, 1 ],
            [ 1, 0, 1, 0 ] ];
 
    // Number of vertices in the graph
    var N = adj.length;
 
    findNumberOfSimpleCycles(N, adj);
 
// This code is contributed by umadevi9616
</script>

Output:

Time Complexity: O((2^N)N²)
Auxiliary Space: O(1)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

Count of simple cycles in an undirected graph having N vertices

C++

Java

Python3

C#

Javascript

Working with Titles and Heading – Python docx Module

Creating a Receipt Calculator using Python

One Liner for Python if-elif-else Statements

LEAVE A REPLY Cancel reply

Most Popular

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

Interviewed With Kyle Smith – Founder and CEO of Escalated by Shauli Zacks

EDITOR PICKS

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

POPULAR POSTS

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

POPULAR CATEGORY

ABOUT US

FOLLOW US