Producto de longitudes de todos los ciclos en un gráfico no dirigido

Dado un grafo no dirigido y no ponderado. La tarea es encontrar el producto de las longitudes de todos los ciclos formados en él.
Ejemplo 1: 
 

El gráfico anterior tiene dos ciclos de longitud 4 y 3, el producto de las longitudes de ciclo es 12.

Ejemplo 2: 
 

El gráfico anterior tiene dos ciclos de longitud 4 y 3, el producto de las longitudes de ciclo es 12.

Planteamiento: Usando el método de coloreado de gráficos , marca todos los vértices de los diferentes ciclos con números únicos. Una vez que se completa el recorrido del gráfico, empuje todos los números marcados similares a una lista de adyacencia e imprima la lista de adyacencia en consecuencia. A continuación se muestra el algoritmo:
 

  • Inserte los bordes en una lista de adyacencia.
  • Llame a la función DFS que utiliza el método de coloreado para marcar el vértice.
  • Siempre que haya un vértice visitado parcialmente, retroceda hasta alcanzar el vértice actual y márquelos todos con números de ciclo. Una vez que todos los vértices estén marcados, aumente el número de ciclo.
  • Una vez que se completa Dfs, repita los bordes y empuje los mismos bordes de números marcados a otra lista de adyacencia.
  • Iterar en la otra lista de adyacencia y mantener la cuenta del número de vértices en un ciclo usando números de mapa y ciclo
  • Iterar para obtener números de ciclo y multiplicar las longitudes para obtener el producto final que será la respuesta.

A continuación se muestra la implementación del enfoque anterior: 
 

C++

// C++ program to find the
// product of lengths of cycle
#include <bits/stdc++.h>
using namespace std;
const int N = 100000;
 
// variables to be used
// in both functions
vector<int> graph[N];
 
// Function to mark the vertex with
// different colors for different cycles
void dfs_cycle(int u, int p, int color[],
            int mark[], int par[], int& cyclenumber)
{
 
    // already (completely) visited vertex.
    if (color[u] == 2) {
        return;
    }
 
    // seen vertex, but was not completely
    // visited -> cycle detected.
    // backtrack based on parents to find
    // the complete cycle.
    if (color[u] == 1) {
 
        cyclenumber++;
        int cur = p;
        mark[cur] = cyclenumber;
 
        // backtrack the vertex which are
        // in the current cycle thats found
        while (cur != u) {
            cur = par[cur];
            mark[cur] = cyclenumber;
        }
        return;
    }
    par[u] = p;
 
    // partially visited.
    color[u] = 1;
 
    // simple dfs on graph
    for (int v : graph[u]) {
 
        // if it has not been visited previously
        if (v == par[u]) {
            continue;
        }
        dfs_cycle(v, u, color, mark, par, cyclenumber);
    }
 
    // completely visited.
    color[u] = 2;
}
 
// add the edges to the graph
void addEdge(int u, int v)
{
    graph[u].push_back(v);
    graph[v].push_back(u);
}
 
// Function to print the cycles
int productLength(int edges, int mark[], int& cyclenumber)
{
    unordered_map<int, int> mp;
 
    // push the edges that into the
    // cycle adjacency list
    for (int i = 1; i <= edges; i++) {
        if (mark[i] != 0)
            mp[mark[i]]++;
    }
    int cnt = 1;
 
    // product all the length of cycles
    for (int i = 1; i <= cyclenumber; i++) {
        cnt = cnt * mp[i];
    }
    if (cyclenumber == 0)
        cnt = 0;
 
    return cnt;
}
 
// Driver Code
int main()
{
 
    // add edges
    addEdge(1, 2);
    addEdge(2, 3);
    addEdge(3, 4);
    addEdge(4, 6);
    addEdge(4, 7);
    addEdge(5, 6);
    addEdge(3, 5);
    addEdge(7, 8);
    addEdge(6, 10);
    addEdge(5, 9);
    addEdge(10, 11);
    addEdge(11, 12);
    addEdge(11, 13);
    addEdge(12, 13);
 
    // arrays required to color the
    // graph, store the parent of node
    int color[N];
    int par[N];
 
    // mark with unique numbers
    int mark[N];
 
    // store the numbers of cycle
    int cyclenumber = 0;
    int edges = 13;
 
    // call DFS to mark the cycles
    dfs_cycle(1, 0, color, mark, par, cyclenumber);
 
    // function to print the cycles
    cout << productLength(edges, mark, cyclenumber);
 
    return 0;
}

Java

// Java program to find the
// product of lengths of cycle
import java.io.*;
import java.util.*;
 
class GFG
{
    static int N = 100000;
    static int cyclenumber;
 
    // variables to be used
    // in both functions
    //@SuppressWarnings("unchecked")
    static Vector<Integer>[] graph = new Vector[N];
 
    // This static block is used to initialize
    // array of Vector, otherwise it will throw
    // NullPointerException
    static
    {
        for (int i = 0; i < N; i++)
            graph[i] = new Vector<>();
    }
 
    // Function to mark the vertex with
    // different colors for different cycles
    static void dfs_cycle(int u, int p, int[] color,
                          int[] mark, int[] par)
    {
 
        // already (completely) visited vertex.
        if (color[u] == 2)
            return;
 
        // seen vertex, but was not completely
        // visited -> cycle detected.
        // backtrack based on parents to find
        // the complete cycle.
        if (color[u] == 1)
        {
            cyclenumber++;
            int cur = p;
            mark[cur] = cyclenumber;
 
            // backtrack the vertex which are
            // in the current cycle thats found
            while (cur != u)
            {
                cur = par[cur];
                mark[cur] = cyclenumber;
            }
            return;
        }
        par[u] = p;
 
        // partially visited.
        color[u] = 1;
 
        // simple dfs on graph
        for (int v : graph[u])
        {
 
            // if it has not been visited previously
            if (v == par[u])
            {
                continue;
            }
            dfs_cycle(v, u, color, mark, par);
        }
 
        // completely visited.
        color[u] = 2;
    }
 
    // add the edges to the graph
    static void addEdge(int u, int v)
    {
        graph[u].add(v);
        graph[v].add(u);
    }
 
    // Function to print the cycles
    static int productLength(int edges, int[] mark)
    {
        HashMap<Integer,
                Integer> mp = new HashMap<>();
 
        // push the edges that into the
        // cycle adjacency list
        for (int i = 1; i <= edges; i++)
        {
            if (mark[i] != 0)
            {
                mp.put(mark[i], mp.get(mark[i]) == null ?
                                1 : mp.get(mark[i]) + 1);
            }
        }
        int cnt = 1;
 
        // product all the length of cycles
        for (int i = 1; i <= cyclenumber; i++)
        {
            cnt = cnt * mp.get(i);
        }
        if (cyclenumber == 0)
            cnt = 0;
 
        return cnt;
    }
 
    // Driver Code
    public static void main(String[] args) throws IOException
    {
 
        // add edges
        addEdge(1, 2);
        addEdge(2, 3);
        addEdge(3, 4);
        addEdge(4, 6);
        addEdge(4, 7);
        addEdge(5, 6);
        addEdge(3, 5);
        addEdge(7, 8);
        addEdge(6, 10);
        addEdge(5, 9);
        addEdge(10, 11);
        addEdge(11, 12);
        addEdge(11, 13);
        addEdge(12, 13);
 
        // arrays required to color the
        // graph, store the parent of node
        int[] color = new int[N];
        int[] par = new int[N];
 
        // mark with unique numbers
        int[] mark = new int[N];
 
        // store the numbers of cycle
        cyclenumber = 0;
        int edges = 13;
 
        // call DFS to mark the cycles
        dfs_cycle(1, 0, color, mark, par);
 
        // function to print the cycles
        System.out.println(productLength(edges, mark));
    }
}
 
// This code is contributed by
// sanjeev2552

Python3

# Python3 program to find the
# product of lengths of cycle
from collections import defaultdict
 
# Function to mark the vertex with
# different colors for different cycles
def dfs_cycle(u, p, color, mark, par):
 
    global cyclenumber
     
    # already (completely) visited vertex.
    if color[u] == 2:
        return
 
    # seen vertex, but was not completely
    # visited -> cycle detected.
    # backtrack based on parents to find
    # the complete cycle.
    if color[u] == 1:
 
        cyclenumber += 1
        cur = p
        mark[cur] = cyclenumber
 
        # backtrack the vertex which are
        # in the current cycle thats found
        while cur != u:
            cur = par[cur]
            mark[cur] = cyclenumber
         
        return
     
    par[u] = p
 
    # partially visited.
    color[u] = 1
 
    # simple dfs on graph
    for v in graph[u]:
 
        # if it has not been visited previously
        if v == par[u]:
            continue
         
        dfs_cycle(v, u, color, mark, par)
     
    # completely visited.
    color[u] = 2
 
# add the edges to the graph
def addEdge(u, v):
 
    graph[u].append(v)
    graph[v].append(u)
 
# Function to print the cycles
def productLength(edges, mark, cyclenumber):
 
    mp = defaultdict(lambda:0)
 
    # push the edges that into the
    # cycle adjacency list
    for i in range(1, edges+1):
        if mark[i] != 0:
            mp[mark[i]] += 1
     
    cnt = 1
 
    # product all the length of cycles
    for i in range(1, cyclenumber + 1):
        cnt = cnt * mp[i]
     
    if cyclenumber == 0:
        cnt = 0
 
    return cnt
 
# Driver Code
if __name__ == "__main__":
     
    N = 100000
    graph = [[] for i in range(N)]
 
    # add edges
    addEdge(1, 2)
    addEdge(2, 3)
    addEdge(3, 4)
    addEdge(4, 6)
    addEdge(4, 7)
    addEdge(5, 6)
    addEdge(3, 5)
    addEdge(7, 8)
    addEdge(6, 10)
    addEdge(5, 9)
    addEdge(10, 11)
    addEdge(11, 12)
    addEdge(11, 13)
    addEdge(12, 13)
 
    # arrays required to color the
    # graph, store the parent of node
    color, par = [None] * N, [None] * N
 
    # mark with unique numbers
    mark = [None] * N
 
    # store the numbers of cycle
    cyclenumber, edges = 0, 13
 
    # call DFS to mark the cycles
    dfs_cycle(1, 0, color, mark, par)
 
    # function to print the cycles
    print(productLength(edges, mark,
                        cyclenumber))
 
# This code is contributed by Rituraj Jain

C#

// C# program to find the
// product of lengths of cycle
using System;
using System.Collections.Generic;
 
class GFG
{
    static int N = 100000;
    static int cyclenumber;
 
    // variables to be used
    // in both functions
    //@SuppressWarnings("unchecked")
    static List<int>[] graph = new List<int>[N];
 
    // This static block is used to initialize
    // array of List, otherwise it will throw
    // NullPointerException
 
 
    // Function to mark the vertex with
    // different colors for different cycles
    static void dfs_cycle(int u, int p, int[] color,
                        int[] mark, int[] par)
    {
 
        // already (completely) visited vertex.
        if (color[u] == 2)
            return;
 
        // seen vertex, but was not completely
        // visited -> cycle detected.
        // backtrack based on parents to find
        // the complete cycle.
        if (color[u] == 1)
        {
            cyclenumber++;
            int cur = p;
            mark[cur] = cyclenumber;
 
            // backtrack the vertex which are
            // in the current cycle thats found
            while (cur != u)
            {
                cur = par[cur];
                mark[cur] = cyclenumber;
            }
            return;
        }
        par[u] = p;
 
        // partially visited.
        color[u] = 1;
 
        // simple dfs on graph
        foreach (int v in graph[u])
        {
 
            // if it has not been visited previously
            if (v == par[u])
            {
                continue;
            }
            dfs_cycle(v, u, color, mark, par);
        }
 
        // completely visited.
        color[u] = 2;
    }
 
    // add the edges to the graph
    static void addEdge(int u, int v)
    {
        graph[u].Add(v);
        graph[v].Add(u);
    }
 
    // Function to print the cycles
    static int productLength(int edges, int[] mark)
    {
        Dictionary<int,int> mp = new Dictionary<int,int>();
         
 
        // push the edges that into the
        // cycle adjacency list
        for (int i = 1; i <= edges; i++)
        {
            if (mark[i] != 0)
            {
                    if(mp.ContainsKey(mark[i]))
                        mp[mark[i]] = mp[mark[i]] + 1;
                    else
                        mp.Add(mark[i], 1);
 
             
                             
            }
        }
        int cnt = 1;
 
        // product all the length of cycles
        for (int i = 1; i <= cyclenumber; i++)
        {
            cnt = cnt * mp[i];
        }
        if (cyclenumber == 0)
            cnt = 0;
 
        return cnt;
    }
 
    // Driver Code
    public static void Main(String[] args)
    {
 
        for (int i = 0; i < N; i++)
            graph[i] = new List<int>();
         
        // add edges
        addEdge(1, 2);
        addEdge(2, 3);
        addEdge(3, 4);
        addEdge(4, 6);
        addEdge(4, 7);
        addEdge(5, 6);
        addEdge(3, 5);
        addEdge(7, 8);
        addEdge(6, 10);
        addEdge(5, 9);
        addEdge(10, 11);
        addEdge(11, 12);
        addEdge(11, 13);
        addEdge(12, 13);
 
        // arrays required to color the
        // graph, store the parent of node
        int[] color = new int[N];
        int[] par = new int[N];
 
        // mark with unique numbers
        int[] mark = new int[N];
 
        // store the numbers of cycle
        cyclenumber = 0;
        int edges = 13;
 
        // call DFS to mark the cycles
        dfs_cycle(1, 0, color, mark, par);
 
        // function to print the cycles
        Console.WriteLine(productLength(edges, mark));
    }
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
 
// JavaScript program to find the
// product of lengths of cycle
var N = 100000;
var cyclenumber;
 
// variables to be used
// in both functions
//@SuppressWarnings("unchecked")
var graph = Array.from(Array(N), ()=>Array());
 
// This static block is used to initialize
// array of List, otherwise it will throw
// NullPointerException
 
// Function to mark the vertex with
// different colors for different cycles
function dfs_cycle(u, p, color, mark, par)
{
    // already (completely) visited vertex.
    if (color[u] == 2)
        return;
    // seen vertex, but was not completely
    // visited -> cycle detected.
    // backtrack based on parents to find
    // the complete cycle.
    if (color[u] == 1)
    {
        cyclenumber++;
        var cur = p;
        mark[cur] = cyclenumber;
        // backtrack the vertex which are
        // in the current cycle thats found
        while (cur != u)
        {
            cur = par[cur];
            mark[cur] = cyclenumber;
        }
        return;
    }
    par[u] = p;
    // partially visited.
    color[u] = 1;
    // simple dfs on graph
    for(var v of graph[u])
    {
        // if it has not been visited previously
        if (v == par[u])
        {
            continue;
        }
        dfs_cycle(v, u, color, mark, par);
    }
    // completely visited.
    color[u] = 2;
}
// add the edges to the graph
function addEdge(u, v)
{
    graph[u].push(v);
    graph[v].push(u);
}
// Function to print the cycles
function productLength(edges, mark)
{
    var mp = new Map();
     
    // push the edges that into the
    // cycle adjacency list
    for (var i = 1; i <= edges; i++)
    {
        if (mark[i] != 0)
        {
          if(mp.has(mark[i]))
              mp.set(mark[i], mp.get(mark[i])+1);
          else
              mp.set(mark[i], 1);      
        }
    }
    var cnt = 1;
    // product all the length of cycles
    for (var i = 1; i <= cyclenumber; i++)
    {
        cnt = cnt * mp.get(i);
    }
    if (cyclenumber == 0)
        cnt = 0;
    return cnt;
}
// Driver Code
// add edges
addEdge(1, 2);
addEdge(2, 3);
addEdge(3, 4);
addEdge(4, 6);
addEdge(4, 7);
addEdge(5, 6);
addEdge(3, 5);
addEdge(7, 8);
addEdge(6, 10);
addEdge(5, 9);
addEdge(10, 11);
addEdge(11, 12);
addEdge(11, 13);
addEdge(12, 13);
// arrays required to color the
// graph, store the parent of node
var color = Array(N).fill(0);
var par = Array(N).fill(0);
// mark with unique numbers
var mark = Array(N).fill(0);
// store the numbers of cycle
cyclenumber = 0;
var edges = 13;
// call DFS to mark the cycles
dfs_cycle(1, 0, color, mark, par);
// function to print the cycles
document.write(productLength(edges, mark));
 
 
</script>
Producción: 

12

 

Complejidad temporal : O(N), donde N es el número de Nodes del gráfico.
 

Publicación traducida automáticamente

Artículo escrito por Striver y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *