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.