Dado un gráfico no ponderado no dirigido de N vértices en forma de array de adyacencia adj[][] , la tarea es encontrar el número de ciclos simples en él.
Entrada: adj[][] = { { 0, 1, 1, 1 }, { 1, 0, 1, 0 }, { 1, 1, 0, 1 }, { 1, 0, 1, 0 } }
Salida : 2
Explicación: El gráfico se muestra a continuación como:
El gráfico dado consta de dos ciclos simples como se muestra
Entrada: adj[][] = { { 0, 1, 1, 0 }, { 1, 0, 0, 1 }, { 1, 0, 0, 1 }, { 0, 1, 1, 0 } } Salida: 1
Enfoque: el problema dado se puede resolver mediante el uso de programación dinámica con máscara de bits , el estado de programación dinámica para las rutas hamiltonianas se define como dp [máscara] [i] como el número de rutas que cubren la máscara del conjunto de Nodes y termina en i e itere de 0 a N-1 y en cada iteración, calcule el número de bucles que contienen el Node actual sin el Node anterior y súmelos. Dado que hay dos direcciones para un bucle, divida el resultado entre 2 . Siga los pasos a continuación para resolver el problema:
- Inicialice una variable ans como 0 que almacene el recuento de ciclos resultante.
- Inicialice una array 2-D dp[][] array de dimensiones 2 N y N e inicialícela con 0 .
- Iterar sobre el rango [0, 2 N – 1) usando la máscara variable y realizar las siguientes tareas:
- Inicialice 2 variables nodeSet y firstSetBit como el número de bits establecidos y el primer bit establecido en la máscara .
- Si nodeSet es igual a 1, establezca el valor de dp[mask][firstSetBit] como 1 .
- Ahora, para cada máscara que tenga bits establecidos mayores que 1 , itere sobre el rango [firstSetBit + 1, N – 1) usando la variable j y si Bitwise AND de mask & 2 j es verdadero , entonces inicialice una variable newNodeSet como máscara^ 2 j e itere sobre el rango [0, N) usando la variable k y realice las siguientes tareas:
- Compruebe si hay un borde entre los Nodes k y j ( k no es igual a j) .
- Si hay un borde, agregue el número de bucles en esta máscara que termina en k y no contiene j al estado de la máscara de conjunto de Nodes de la siguiente manera dp[máscara][j] = dp[máscara][j]+ dp[máscara XOR 2 j ][k] .
- Si adj[j][firstSetBit] es 1 y nodeSet es mayor que 2, agregue el valor de dp[mask][j] a la variable ans .
- Después de realizar los pasos anteriores, imprima el valor de ans como respuesta.
A continuación se muestra la implementación del enfoque anterior.
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>
Producción:
2
Complejidad de Tiempo: O((2 N )N 2 )
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por ramandeep8421 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA