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> |
Output:
2
Time Complexity: O((2N)N2)
Auxiliary Space: O(1)
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!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
