Recuento de todos los ciclos sin ningún ciclo interno en un gráfico dado

Dado un gráfico no dirigido que consta de N vértices numerados [0, N-1] y E aristas, la tarea es contar el número de ciclos de modo que cualquier subconjunto de vértices de un ciclo no forme otro ciclo.
Ejemplos: 
 

Entrada: N = 2, E = 2, aristas = [{0, 1}, {1, 0}] 
Salida: 1 
Explicación: 
Solo existe un ciclo entre los dos vértices. 
 

Entrada: N = 6, E = 9, bordes = [{0, 1}, {1, 2}, {0, 2}, {3, 0}, {3, 2}, {4, 1}, { 4, 2}, {5, 1}, {5, 0}] 
Salida: 4 
Explicación: 
Los ciclos posibles se muestran en el siguiente diagrama: 
 

Los ciclos como 5 -> 0 -> 2 -> 1 -> 5 no se consideran, ya que se compone de ciclos internos {5 -> 0 -> 1} y {0 -> 1 -> 2} 
 

Enfoque: 
dado que los vértices V requieren aristas V para formar 1 ciclo, el número de ciclos necesarios se puede expresar mediante la fórmula: 
 

(Edges - Vertices) + 1

Ilustración: 
 

N = 6, E = 9, aristas = [{0, 1}, {1, 2}, {0, 2}, {3, 0}, {3, 2}, {4, 1}, {4, 2}, {5, 1}, {5, 0}] 
Número de ciclos = 9 – 6 + 1 = 4 
Los 4 ciclos en el gráfico son: 
{5, 0, 1}, {0, 1, 2}, {3, 0, 2} y {1, 2, 4} 
 

Esta fórmula también cubre el caso en que un solo vértice puede tener un bucle propio. 
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation for the
// above approach.
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the
// count of required cycles
int numberOfCycles(int N, int E,
                   int edges[][2])
{
    vector<int> graph[N];
    for (int i = 0; i < E; i++) {
        graph[edges[i][0]]
            .push_back(edges[i][1]);
        graph[edges[i][1]]
            .push_back(edges[i][0]);
    }
 
    // Return the number of cycles
    return (E - N) + 1;
}
 
// Driver Code
int main()
{
    int N = 6;
    int E = 9;
    int edges[][2] = { { 0, 1 },
                       { 1, 2 },
                       { 2, 0 },
                       { 5, 1 },
                       { 5, 0 },
                       { 3, 0 },
                       { 3, 2 },
                       { 4, 2 },
                       { 4, 1 } };
    int k = numberOfCycles(N, E,
                           edges);
 
    cout << k << endl;
    return 0;
}

// Java implementation for the
// above approach.
import java.util.*;
 
class GFG{
 
// Function to return the
// count of required cycles
static int numberOfCycles(int N, int E,
                          int edges[][])
{
    @SuppressWarnings("unchecked")
    Vector<Integer> []graph = new Vector[N];
    for(int i = 0; i < N; i++)
        graph[i] = new Vector<Integer>();
         
    for(int i = 0; i < E; i++)
    {
        graph[edges[i][0]].add(edges[i][1]);
        graph[edges[i][1]].add(edges[i][0]);
    }
 
    // Return the number of cycles
    return (E - N) + 1;
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 6;
    int E = 9;
    int edges[][] = { { 0, 1 },
                      { 1, 2 },
                      { 2, 0 },
                      { 5, 1 },
                      { 5, 0 },
                      { 3, 0 },
                      { 3, 2 },
                      { 4, 2 },
                      { 4, 1 } };
                       
    int k = numberOfCycles(N, E, edges);
 
    System.out.print(k + "\n");
}
}
 
// This code is contributed by Amit Katiyar

# Python3 implementation for the
# above approach.
  
# Function to return the
# count of required cycles
def numberOfCycles(N, E, edges):
 
    graph=[[] for i in range(N)]
     
    for i in range(E):
     
        graph[edges[i][0]].append(edges[i][1]);
        graph[edges[i][1]].append(edges[i][0]);
  
    # Return the number of cycles
    return (E - N) + 1;
  
# Driver Code
if __name__=='__main__':
     
    N = 6;
    E = 9;
    edges = [ [ 0, 1 ],
                       [ 1, 2 ],
                       [ 2, 0 ],
                       [ 5, 1 ],
                       [ 5, 0 ],
                       [ 3, 0 ],
                       [ 3, 2 ],
                       [ 4, 2 ],
                       [ 4, 1 ] ];
     
    k = numberOfCycles(N, E,edges);
    print(k)
     
    # This code is contributed by rutvik_56

// C# implementation for the
// above approach.
using System;
using System.Collections.Generic;
class GFG{
 
// Function to return the
// count of required cycles
static int numberOfCycles(int N, int E,
                          int [,]edges)
{
 
    List<int> []graph = new List<int>[N];
    for(int i = 0; i < N; i++)
        graph[i] = new List<int>();
         
    for(int i = 0; i < E; i++)
    {
        graph[edges[i, 0]].Add(edges[i, 1]);
        graph[edges[i, 1]].Add(edges[i, 0]);
    }
 
    // Return the number of cycles
    return (E - N) + 1;
}
 
// Driver Code
public static void Main(String[] args)
{
    int N = 6;
    int E = 9;
    int [,]edges = { { 0, 1 }, { 1, 2 },
                     { 2, 0 }, { 5, 1 },
                     { 5, 0 }, { 3, 0 },
                     { 3, 2 }, { 4, 2 },
                     { 4, 1 } };
                       
    int k = numberOfCycles(N, E, edges);
 
    Console.Write(k + "\n");
}
}
 
// This code is contributed by Rohit_ranjan

<script>
 
// JavaScript implementation for the
// above approach.
 
// Function to return the
// count of required cycles
function numberOfCycles(N, E, edges)
{
    var graph = Array.from(Array(N), ()=> Array());
    for (var i = 0; i < E; i++) {
        graph[edges[i][0]]
            .push(edges[i][1]);
        graph[edges[i][1]]
            .push(edges[i][0]);
    }
 
    // Return the number of cycles
    return (E - N) + 1;
}
 
// Driver Code
var N = 6;
var E = 9;
var edges = [ [ 0, 1 ],
                   [ 1, 2 ],
                   [ 2, 0 ],
                   [ 5, 1 ],
                   [ 5, 0 ],
                   [ 3, 0 ],
                   [ 3, 2 ],
                   [ 4, 2 ],
                   [ 4, 1 ] ];
                    
var k = numberOfCycles(N, E,
                       edges);
document.write( k);
 
</script>

4

Complejidad temporal: O(E) 
Espacio auxiliar: O(N)