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 2N and N and initialize it with 0.
- Iterate over the range [0, 2N – 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 & 2j is true, then initialize a variable newNodeSet as mask^2j 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 2j][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 graphvoid 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 Codeint 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 approachimport 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 graphstatic 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 Codepublic 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 bitdef __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 graphdef 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 codeif __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 approachusing 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 graphstatic 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 Codepublic 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 graphfunction 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> |
Â
Â
2
Â
Â
Time Complexity: O((2N)N2)
Auxiliary Space: O(1)
Â
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

