Dado un gráfico no dirigido de n Nodes y m aristas. La tarea es encontrar los bordes mínimos necesarios para hacer el circuito de Euler en el gráfico dado.
Ejemplos:
Input : n = 3,
m = 2
Edges[] = {{1, 2}, {2, 3}}
Output : 1
By connecting 1 to 3, we can create a Euler Circuit.
Para que exista un circuito de Euler en el gráfico, requerimos que cada Node tenga un grado par porque entonces existe un borde que se puede usar para salir del Node después de ingresar.
Ahora, puede haber dos casos:
1. Hay un componente conectado en el gráfico
. En este caso, si todos los Nodes en el gráfico son de grado par, entonces decimos que el gráfico ya tiene un circuito de Euler y no necesitamos para agregar cualquier borde en él. Pero si hay algún Node con un grado impar, debemos agregar bordes.
Puede haber un número par de vértices de grado impar en el gráfico. Esto se puede demostrar fácilmente por el hecho de que la suma de los grados del Node de grados pares y los grados del Node de grados impares debe coincidir con los grados totales que siempre son pares, ya que cada arista aporta dos a esta suma. Ahora, si emparejamos Nodes aleatorios de grado impar en el gráfico y agregamos un borde entre ellos, podemos hacer que todos los Nodes tengan un grado par y, por lo tanto, hacer que exista un circuito de Euler.
2. Hay componentes desconectados en el gráfico
. Primero marcamos el componente como par e impar. Los componentes impares son aquellos que tienen al menos un Node de grado impar. Tome todos los componentes pares y seleccione un vértice aleatorio de cada componente y alinéelos linealmente. Ahora agregamos un borde entre vértices adyacentes. Así que hemos conectado los componentes pares y hemos creado componentes impares equivalentes que tienen dos Nodes con grado impar.
Ahora, para tratar con componentes impares, es decir, componentes con al menos un Node de grado impar. Podemos conectar todos estos componentes impares usando aristas cuyo número es igual al número de componentes desconectados. Esto se puede hacer colocando los componentes en orden cíclico y eligiendo dos Nodes de grado impar de cada componente y usándolos para conectarlos a los componentes de cualquier lado. Ahora tenemos un único componente conexo del que ya hemos hablado.
A continuación se muestra la implementación de este enfoque:
C++
// C++ program to find minimum edge required
// to make Euler Circuit
#include <bits/stdc++.h>
using namespace std;
// Depth-First Search to find a connected
// component
void dfs(vector<int> g[], int vis[], int odd[],
int deg[], int comp, int v)
{
vis[v] = 1;
if (deg[v]%2 == 1)
odd[comp]++;
for (int u : g[v])
if (vis[u] == 0)
dfs(g, vis, odd, deg, comp, u);
}
// Return minimum edge required to make Euler
// Circuit
int minEdge(int n, int m, int s[], int d[])
{
// g : to store adjacency list
// representation of graph.
// e : to store list of even degree vertices
// o : to store list of odd degree vertices
vector<int> g[n+1], e, o;
int deg[n+1]; // Degrees of vertices
int vis[n+1]; // To store visited in DFS
int odd[n+1]; // Number of odd nodes in components
memset(deg, 0, sizeof(deg));
memset(vis, 0, sizeof(vis));
memset(odd, 0, sizeof(odd));
for (int i = 0; i < m; i++)
{
g[s[i]].push_back(d[i]);
g[d[i]].push_back(s[i]);
deg[s[i]]++;
deg[d[i]]++;
}
// 'ans' is result and 'comp' is component id
int ans = 0, comp = 0;
for (int i = 1; i <= n; i++)
{
if (vis[i]==0)
{
comp++;
dfs(g, vis, odd, deg, comp, i);
// Checking if connected component
// is odd.
if (odd[comp] == 0)
e.push_back(comp);
// Checking if connected component
// is even.
else
o.push_back(comp);
}
}
// If whole graph is a single connected
// component with even degree.
if (o.size() == 0 && e.size() == 1)
return 0;
// If all connected component is even
if (o.size() == 0)
return e.size();
// If graph have atleast one even connected
// component
if (e.size() != 0)
ans += e.size();
// For all the odd connected component.
for (int i : o)
ans += odd[i]/2;
return ans;
}
// Driven Program
int main()
{
int n = 3, m = 2;
int source[] = { 1, 2 };
int destination[] = { 2, 3 };
cout << minEdge(n, m, source, destination) << endl;
return 0;
}
Java
// Java program to find minimum edge
// required to make Euler Circuit
import java.io.*;
import java.util.*;
class GFG
{
// Depth-First Search to find
// a connected component
static void dfs(Vector<Integer>[] g, int[] vis,
int[] odd, int[] deg,
int comp, int v)
{
vis[v] = 1;
if (deg[v] % 2 == 1)
odd[comp]++;
for (int u : g[v])
if (vis[u] == 0)
dfs(g, vis, odd, deg, comp, u);
}
// Return minimum edge required
// to make Euler Circuit
static int minEdge(int n, int m,
int[] s, int[] d)
{
// g : to store adjacency list
// representation of graph.
// e : to store list of even degree vertices
// o : to store list of odd degree vertices
@SuppressWarnings("unchecked")
Vector<Integer>[] g = new Vector[n + 1];
Vector<Integer> e = new Vector<>();
Vector<Integer> o = new Vector<>();
for (int i = 0; i < n + 1; i++)
g[i] = new Vector<>();
// Degrees of vertices
int[] deg = new int[n + 1];
// To store visited in DFS
int[] vis = new int[n + 1];
// Number of odd nodes in components
int[] odd = new int[n + 1];
Arrays.fill(deg, 0);
Arrays.fill(vis, 0);
Arrays.fill(odd, 0);
for (int i = 0; i < m; i++)
{
g[s[i]].add(d[i]);
g[d[i]].add(s[i]);
deg[s[i]]++;
deg[d[i]]++;
}
// 'ans' is result and
// 'comp' is component id
int ans = 0, comp = 0;
for (int i = 1; i <= n; i++)
{
if (vis[i] == 0)
{
comp++;
dfs(g, vis, odd, deg, comp, i);
// Checking if connected component
// is odd.
if (odd[comp] == 0)
e.add(comp);
// Checking if connected component
// is even.
else
o.add(comp);
}
}
// If whole graph is a single connected
// component with even degree.
if (o.size() == 0 && e.size() == 1)
return 0;
// If all connected component is even
if (o.size() == 0)
return e.size();
// If graph have atleast one
// even connected component
if (e.size() != 0)
ans += e.size();
// For all the odd connected component.
for (int i : o)
ans += odd[i] / 2;
return ans;
}
// Driver Code
public static void main(String[] args) throws IOException
{
int n = 3, m = 2;
int[] source = { 1, 2 };
int[] destination = { 2, 3 };
System.out.println(minEdge(n, m, source,
destination));
}
}
// This code is contributed by
// sanjeev2552
Python3
# Python3 program to find minimum edge # required to make Euler Circuit # Depth-First Search to find a # connected component def dfs(g, vis, odd, deg, comp, v): vis[v] = 1 if (deg[v] % 2 == 1): odd[comp] += 1 for u in range(len(g[v])): if (vis[u] == 0): dfs(g, vis, odd, deg, comp, u) # Return minimum edge required to # make Euler Circuit def minEdge(n, m, s, d): # g : to store adjacency list # representation of graph. # e : to store list of even degree vertices # o : to store list of odd degree vertices g = [[] for i in range(n + 1)] e = [] o = [] deg = [0] * (n + 1) # Degrees of vertices vis = [0] * (n + 1) # To store visited in DFS odd = [0] * (n + 1) # Number of odd nodes # in components for i in range(m): g[s[i]].append(d[i]) g[d[i]].append(s[i]) deg[s[i]] += 1 deg[d[i]] += 1 # 'ans' is result and 'comp' # is component id ans = 0 comp = 0 for i in range(1, n + 1): if (vis[i] == 0): comp += 1 dfs(g, vis, odd, deg, comp, i) # Checking if connected component # is odd. if (odd[comp] == 0): e.append(comp) # Checking if connected component # is even. else: o.append(comp) # If whole graph is a single connected # component with even degree. if (len(o) == 0 and len(e) == 1): return 0 # If all connected component is even if (len(o) == 0): return len(e) # If graph have atleast one # even connected component if (len(e) != 0): ans += len(e) # For all the odd connected component. for i in range(len(o)): ans += odd[i] // 2 return ans # Driver Code if __name__ == '__main__': n = 3 m = 2 source = [ 1, 2 ] destination = [ 2, 3] print(minEdge(n, m, source, destination)) # This code is contributed by PranchalK
Producción:
1
Este artículo es una contribución de Anuj Chauhan . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA