Dado un gráfico ponderado y no dirigido, necesitamos encontrar si existe un ciclo en este gráfico tal que la suma de los pesos de todos los bordes en ese ciclo resulte impar.
Ejemplos:
Input : Number of vertices, n = 4,
Number of edges, m = 4
Weighted Edges =
1 2 12
2 3 1
4 3 1
4 1 20
Output : No! There is no odd weight
cycle in the given graph
Input : Number of vertices, n = 5,
Number of edges, m = 3
Weighted Edges =
1 2 1
3 2 1
3 1 1
Output : Yes! There is an odd weight
cycle in the given graph
La solución se basa en el hecho de que » Si un gráfico no tiene un ciclo de longitud impar, entonces debe ser bipartito, es decir, puede colorearse con dos colores «.
La idea es convertir el problema dado en un problema más simple en el que solo tenemos que verificar si hay ciclo de duración impar o no. Para convertir, hacemos lo siguiente
- Convierta todos los bordes de peso uniforme en dos bordes de peso unitario.
- Convierta todos los bordes de peso impar en un solo borde de peso unitario.
Hagamos otro gráfico para el gráfico que se muestra arriba (en el ejemplo 1)
Aquí, los bordes [1 — 2] se han dividido en dos partes, de modo que [1-pseudo1-2] se ha introducido un pseudoNode. Estamos haciendo esto para que cada uno de nuestros bordes con peso par se tenga en cuenta dos veces, mientras que el borde con peso impar se cuenta solo una vez. Hacer esto nos ayudaría aún más cuando coloreamos nuestro ciclo. Asignamos todos los bordes con peso 1 y luego, usando el método de 2 colores, recorremos todo el gráfico.
Ahora comenzamos a colorear nuestro gráfico modificado usando solo dos colores. En un ciclo con número par de Nodes, cuando lo coloreamos usando solo dos colores, ninguno de los dos bordes adyacentes tiene el mismo color. Mientras que si tratamos de colorear un ciclo que tiene un número impar de aristas, seguramente surge una situación en la que dos aristas adyacentes tienen el mismo color. ¡Esta es nuestra elección! Por lo tanto, si podemos colorear el gráfico modificado completamente usando 2 colores solo de manera que no se les asigne el mismo color a dos bordes adyacentes, entonces no debe haber ningún ciclo en el gráfico o un ciclo con un número par de Nodes. Si surge algún conflicto al colorear un ciclo con solo 2 colores, entonces tenemos un ciclo impar en nuestro gráfico.
Implementación:
C++
// C++ program to check if there is a cycle of
// total odd weight
#include <bits/stdc++.h>
using namespace std;
// This function returns true if the current subpart
// of the forest is two colorable, else false.
bool twoColorUtil(vector<int>G[], int src, int N,
int colorArr[]) {
// Assign first color to source
colorArr[src] = 1;
// Create a queue (FIFO) of vertex numbers and
// enqueue source vertex for BFS traversal
queue <int> q;
q.push(src);
// Run while there are vertices in queue
// (Similar to BFS)
while (!q.empty()){
int u = q.front();
q.pop();
// Find all non-colored adjacent vertices
for (int v = 0; v < G[u].size(); ++v){
// An edge from u to v exists and
// destination v is not colored
if (colorArr[G[u][v]] == -1){
// Assign alternate color to this
// adjacent v of u
colorArr[G[u][v]] = 1 - colorArr[u];
q.push(G[u][v]);
}
// An edge from u to v exists and destination
// v is colored with same color as u
else if (colorArr[G[u][v]] == colorArr[u])
return false;
}
}
return true;
}
// This function returns true if graph G[V][V] is two
// colorable, else false
bool twoColor(vector<int>G[], int N){
// Create a color array to store colors assigned
// to all vertices. Vertex number is used as index
// in this array. The value '-1' of colorArr[i]
// is used to indicate that no color is assigned
// to vertex 'i'. The value 1 is used to indicate
// first color is assigned and value 0 indicates
// second color is assigned.
int colorArr[N];
for (int i = 1; i <= N; ++i)
colorArr[i] = -1;
// As we are dealing with graph, the input might
// come as a forest, thus start coloring from a
// node and if true is returned we'll know that
// we successfully colored the subpart of our
// forest and we start coloring again from a new
// uncolored node. This way we cover the entire forest.
for (int i = 1; i <= N; i++)
if (colorArr[i] == -1)
if (twoColorUtil(G, i, N, colorArr) == false)
return false;
return true;
}
// Returns false if an odd cycle is present else true
// int info[][] is the information about our graph
// int n is the number of nodes
// int m is the number of informations given to us
bool isOddSum(int info[][3],int n,int m){
// Declaring adjacency list of a graph
// Here at max, we can encounter all the edges with
// even weight thus there will be 1 pseudo node
// for each edge
vector<int> G[2*n];
int pseudo = n+1;
int pseudo_count = 0;
for (int i=0; i<m; i++){
// For odd weight edges, we directly add it
// in our graph
if (info[i][2]%2 == 1){
int u = info[i][0];
int v = info[i][1];
G[u].push_back(v);
G[v].push_back(u);
}
// For even weight edges, we break it
else{
int u = info[i][0];
int v = info[i][1];
// Entering a pseudo node between u---v
G[u].push_back(pseudo);
G[pseudo].push_back(u);
G[v].push_back(pseudo);
G[pseudo].push_back(v);
// Keeping a record of number of pseudo nodes
// inserted
pseudo_count++;
// Making a new pseudo node for next time
pseudo++;
}
}
// We pass number graph G[][] and total number
// of node = actual number of nodes + number of
// pseudo nodes added.
return twoColor(G,n+pseudo_count);
}
// Driver function
int main() {
// 'n' correspond to number of nodes in our
// graph while 'm' correspond to the number
// of information about this graph.
int n = 4, m = 4;
int info[4][3] = {{1, 2, 12},
{2, 3, 1},
{4, 3, 1},
{4, 1, 20}};
// This function break the even weighted edges in
// two parts. Makes the adjacency representation
// of the graph and sends it for two coloring.
if (isOddSum(info, n, m) == true)
cout << "No\n";
else
cout << "Yes\n";
return 0;
}
Java
// Java program to check if there is
// a cycle of total odd weight
import java.io.*;
import java.util.*;
class GFG
{
// This function returns true if the current subpart
// of the forest is two colorable, else false.
static boolean twoColorUtil(Vector<Integer>[] G,
int src, int N,
int[] colorArr)
{
// Assign first color to source
colorArr[src] = 1;
// Create a queue (FIFO) of vertex numbers and
// enqueue source vertex for BFS traversal
Queue<Integer> q = new LinkedList<>();
q.add(src);
// Run while there are vertices in queue
// (Similar to BFS)
while (!q.isEmpty())
{
int u = q.peek();
q.poll();
// Find all non-colored adjacent vertices
for (int v = 0; v < G[u].size(); ++v)
{
// An edge from u to v exists and
// destination v is not colored
if (colorArr[G[u].elementAt(v)] == -1)
{
// Assign alternate color to this
// adjacent v of u
colorArr[G[u].elementAt(v)] = 1 - colorArr[u];
q.add(G[u].elementAt(v));
}
// An edge from u to v exists and destination
// v is colored with same color as u
else if (colorArr[G[u].elementAt(v)] == colorArr[u])
return false;
}
}
return true;
}
// This function returns true if
// graph G[V][V] is two colorable, else false
static boolean twoColor(Vector<Integer>[] G, int N)
{
// Create a color array to store colors assigned
// to all vertices. Vertex number is used as index
// in this array. The value '-1' of colorArr[i]
// is used to indicate that no color is assigned
// to vertex 'i'. The value 1 is used to indicate
// first color is assigned and value 0 indicates
// second color is assigned.
int[] colorArr = new int[N + 1];
for (int i = 1; i <= N; ++i)
colorArr[i] = -1;
// As we are dealing with graph, the input might
// come as a forest, thus start coloring from a
// node and if true is returned we'll know that
// we successfully colored the subpart of our
// forest and we start coloring again from a new
// uncolored node. This way we cover the entire forest.
for (int i = 1; i <= N; i++)
if (colorArr[i] == -1)
if (twoColorUtil(G, i, N, colorArr) == false)
return false;
return true;
}
// Returns false if an odd cycle is present else true
// int info[][] is the information about our graph
// int n is the number of nodes
// int m is the number of informations given to us
static boolean isOddSum(int[][] info, int n, int m)
{
// Declaring adjacency list of a graph
// Here at max, we can encounter all the edges with
// even weight thus there will be 1 pseudo node
// for each edge
//@SuppressWarnings("unchecked")
Vector<Integer>[] G = new Vector[2 * n];
for (int i = 0; i < 2 * n; i++)
G[i] = new Vector<>();
int pseudo = n + 1;
int pseudo_count = 0;
for (int i = 0; i < m; i++)
{
// For odd weight edges, we directly add it
// in our graph
if (info[i][2] % 2 == 1)
{
int u = info[i][0];
int v = info[i][1];
G[u].add(v);
G[v].add(u);
}
// For even weight edges, we break it
else
{
int u = info[i][0];
int v = info[i][1];
// Entering a pseudo node between u---v
G[u].add(pseudo);
G[pseudo].add(u);
G[v].add(pseudo);
G[pseudo].add(v);
// Keeping a record of number of
// pseudo nodes inserted
pseudo_count++;
// Making a new pseudo node for next time
pseudo++;
}
}
// We pass number graph G[][] and total number
// of node = actual number of nodes + number of
// pseudo nodes added.
return twoColor(G, n + pseudo_count);
}
// Driver Code
public static void main(String[] args)
{
// 'n' correspond to number of nodes in our
// graph while 'm' correspond to the number
// of information about this graph.
int n = 4, m = 3;
int[][] info = { { 1, 2, 12 }, { 2, 3, 1 },
{ 4, 3, 1 }, { 4, 1, 20 } };
// This function break the even weighted edges in
// two parts. Makes the adjacency representation
// of the graph and sends it for two coloring.
if (isOddSum(info, n, m) == true)
System.out.println("No");
else
System.out.println("Yes");
}
}
// This code is contributed by
// sanjeev2552
Python3
# Python3 program to check if there
# is a cycle of total odd weight
# This function returns true if the current subpart
# of the forest is two colorable, else false.
def twoColorUtil(G, src, N, colorArr):
# Assign first color to source
colorArr[src] = 1
# Create a queue (FIFO) of vertex numbers and
# enqueue source vertex for BFS traversal
q = [src]
# Run while there are vertices in queue
# (Similar to BFS)
while len(q) > 0:
u = q.pop(0)
# Find all non-colored adjacent vertices
for v in range(0, len(G[u])):
# An edge from u to v exists and
# destination v is not colored
if colorArr[G[u][v]] == -1:
# Assign alternate color to this
# adjacent v of u
colorArr[G[u][v]] = 1 - colorArr[u]
q.append(G[u][v])
# An edge from u to v exists and destination
# v is colored with same color as u
elif colorArr[G[u][v]] == colorArr[u]:
return False
return True
# This function returns true if graph
# G[V][V] is two colorable, else false
def twoColor(G, N):
# Create a color array to store colors assigned
# to all vertices. Vertex number is used as index
# in this array. The value '-1' of colorArr[i]
# is used to indicate that no color is assigned
# to vertex 'i'. The value 1 is used to indicate
# first color is assigned and value 0 indicates
# second color is assigned.
colorArr = [-1] * N
# As we are dealing with graph, the input might
# come as a forest, thus start coloring from a
# node and if true is returned we'll know that
# we successfully colored the subpart of our
# forest and we start coloring again from a new
# uncolored node. This way we cover the entire forest.
for i in range(N):
if colorArr[i] == -1:
if twoColorUtil(G, i, N, colorArr) == False:
return False
return True
# Returns false if an odd cycle is present else true
# int info[][] is the information about our graph
# int n is the number of nodes
# int m is the number of informations given to us
def isOddSum(info, n, m):
# Declaring adjacency list of a graph
# Here at max, we can encounter all the
# edges with even weight thus there will
# be 1 pseudo node for each edge
G = [[] for i in range(2*n)]
pseudo, pseudo_count = n+1, 0
for i in range(0, m):
# For odd weight edges, we
# directly add it in our graph
if info[i][2] % 2 == 1:
u, v = info[i][0], info[i][1]
G[u].append(v)
G[v].append(u)
# For even weight edges, we break it
else:
u, v = info[i][0], info[i][1]
# Entering a pseudo node between u---v
G[u].append(pseudo)
G[pseudo].append(u)
G[v].append(pseudo)
G[pseudo].append(v)
# Keeping a record of number
# of pseudo nodes inserted
pseudo_count += 1
# Making a new pseudo node for next time
pseudo += 1
# We pass number graph G[][] and total number
# of node = actual number of nodes + number of
# pseudo nodes added.
return twoColor(G, n+pseudo_count)
# Driver function
if __name__ == "__main__":
# 'n' correspond to number of nodes in our
# graph while 'm' correspond to the number
# of information about this graph.
n, m = 4, 3
info = [[1, 2, 12],
[2, 3, 1],
[4, 3, 1],
[4, 1, 20]]
# This function break the even weighted edges in
# two parts. Makes the adjacency representation
# of the graph and sends it for two coloring.
if isOddSum(info, n, m) == True:
print("No")
else:
print("Yes")
# This code is contributed by Rituraj Jain
C#
// C# program to check if there is
// a cycle of total odd weight
using System;
using System.Collections.Generic;
class GFG
{
// This function returns true if the current subpart
// of the forest is two colorable, else false.
static bool twoColorUtil(List<int>[] G,
int src, int N,
int[] colorArr)
{
// Assign first color to source
colorArr[src] = 1;
// Create a queue (FIFO) of vertex numbers and
// enqueue source vertex for BFS traversal
List<int> q = new List<int>();
q.Add(src);
// Run while there are vertices in queue
// (Similar to BFS)
while (q.Count != 0)
{
int u = q[0];
q.RemoveAt(0);
// Find all non-colored adjacent vertices
for (int v = 0; v < G[u].Count; ++v)
{
// An edge from u to v exists and
// destination v is not colored
if (colorArr[G[u][v]] == -1)
{
// Assign alternate color to this
// adjacent v of u
colorArr[G[u][v]] = 1 - colorArr[u];
q.Add(G[u][v]);
}
// An edge from u to v exists and destination
// v is colored with same color as u
else if (colorArr[G[u][v]] == colorArr[u])
return false;
}
}
return true;
}
// This function returns true if
// graph G[V,V] is two colorable, else false
static bool twoColor(List<int>[] G, int N)
{
// Create a color array to store colors assigned
// to all vertices. Vertex number is used as index
// in this array. The value '-1' of colorArr[i]
// is used to indicate that no color is assigned
// to vertex 'i'. The value 1 is used to indicate
// first color is assigned and value 0 indicates
// second color is assigned.
int[] colorArr = new int[N + 1];
for (int i = 1; i <= N; ++i)
colorArr[i] = -1;
// As we are dealing with graph, the input might
// come as a forest, thus start coloring from a
// node and if true is returned we'll know that
// we successfully colored the subpart of our
// forest and we start coloring again from a new
// uncolored node. This way we cover the entire forest.
for (int i = 1; i <= N; i++)
if (colorArr[i] == -1)
if (twoColorUtil(G, i, N, colorArr) == false)
return false;
return true;
}
// Returns false if an odd cycle is present else true
// int info[,] is the information about our graph
// int n is the number of nodes
// int m is the number of informations given to us
static bool isOddSum(int[,] info, int n, int m)
{
// Declaring adjacency list of a graph
// Here at max, we can encounter all the edges with
// even weight thus there will be 1 pseudo node
// for each edge
//@SuppressWarnings("unchecked")
List<int>[] G = new List<int>[2 * n];
for (int i = 0; i < 2 * n; i++)
G[i] = new List<int>();
int pseudo = n + 1;
int pseudo_count = 0;
for (int i = 0; i < m; i++)
{
// For odd weight edges, we directly add it
// in our graph
if (info[i, 2] % 2 == 1)
{
int u = info[i, 0];
int v = info[i, 1];
G[u].Add(v);
G[v].Add(u);
}
// For even weight edges, we break it
else
{
int u = info[i, 0];
int v = info[i, 1];
// Entering a pseudo node between u---v
G[u].Add(pseudo);
G[pseudo].Add(u);
G[v].Add(pseudo);
G[pseudo].Add(v);
// Keeping a record of number of
// pseudo nodes inserted
pseudo_count++;
// Making a new pseudo node for next time
pseudo++;
}
}
// We pass number graph G[,] and total number
// of node = actual number of nodes + number of
// pseudo nodes added.
return twoColor(G, n + pseudo_count);
}
// Driver Code
public static void Main(String[] args)
{
// 'n' correspond to number of nodes in our
// graph while 'm' correspond to the number
// of information about this graph.
int n = 4, m = 3;
int[,] info = { { 1, 2, 12 }, { 2, 3, 1 },
{ 4, 3, 1 }, { 4, 1, 20 } };
// This function break the even weighted edges in
// two parts. Makes the adjacency representation
// of the graph and sends it for two coloring.
if (isOddSum(info, n, m) == true)
Console.WriteLine("No");
else
Console.WriteLine("Yes");
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// JavaScript program to check if there is
// a cycle of total odd weight
// This function returns true if the current subpart
// of the forest is two colorable, else false.
function twoColorUtil(G, src, N, colorArr)
{
// Assign first color to source
colorArr[src] = 1;
// Create a queue (FIFO) of vertex numbers and
// enqueue source vertex for BFS traversal
var q = [];
q.push(src);
// Run while there are vertices in queue
// (Similar to BFS)
while (q.length != 0)
{
var u = q[0];
q.shift();
// Find all non-colored adjacent vertices
for (var v = 0; v < G[u].length; ++v)
{
// An edge from u to v exists and
// destination v is not colored
if (colorArr[G[u][v]] == -1)
{
// Assign alternate color to this
// adjacent v of u
colorArr[G[u][v]] = 1 - colorArr[u];
q.push(G[u][v]);
}
// An edge from u to v exists and destination
// v is colored with same color as u
else if (colorArr[G[u][v]] == colorArr[u])
return false;
}
}
return true;
}
// This function returns true if
// graph G[V,V] is two colorable, else false
function twoColor(G, N)
{
// Create a color array to store colors assigned
// to all vertices. Vertex number is used as index
// in this array. The value '-1' of colorArr[i]
// is used to indicate that no color is assigned
// to vertex 'i'. The value 1 is used to indicate
// first color is assigned and value 0 indicates
// second color is assigned.
var colorArr = Array(N+1).fill(-1);
// As we are dealing with graph, the input might
// come as a forest, thus start coloring from a
// node and if true is returned we'll know that
// we successfully colored the subpart of our
// forest and we start coloring again from a new
// uncolored node. This way we cover the entire forest.
for (var i = 1; i <= N; i++)
if (colorArr[i] == -1)
if (twoColorUtil(G, i, N, colorArr) == false)
return false;
return true;
}
// Returns false if an odd cycle is present else true
// int info[,] is the information about our graph
// int n is the number of nodes
// int m is the number of informations given to us
function isOddSum(info, n, m)
{
// Declaring adjacency list of a graph
// Here at max, we can encounter all the edges with
// even weight thus there will be 1 pseudo node
// for each edge
//@SuppressWarnings("unchecked")
var G = Array.from(Array(2*n), ()=>Array());
var pseudo = n + 1;
var pseudo_count = 0;
for (var i = 0; i < m; i++)
{
// For odd weight edges, we directly add it
// in our graph
if (info[i][2] % 2 == 1)
{
var u = info[i][0];
var v = info[i][1];
G[u].push(v);
G[v].push(u);
}
// For even weight edges, we break it
else
{
var u = info[i][0];
var v = info[i][1];
// Entering a pseudo node between u---v
G[u].push(pseudo);
G[pseudo].push(u);
G[v].push(pseudo);
G[pseudo].push(v);
// Keeping a record of number of
// pseudo nodes inserted
pseudo_count++;
// Making a new pseudo node for next time
pseudo++;
}
}
// We pass number graph G[,] and total number
// of node = actual number of nodes + number of
// pseudo nodes added.
return twoColor(G, n + pseudo_count);
}
// Driver Code
// 'n' correspond to number of nodes in our
// graph while 'm' correspond to the number
// of information about this graph.
var n = 4, m = 3;
var info = [ [ 1, 2, 12 ], [ 2, 3, 1 ],
[ 4, 3, 1 ], [ 4, 1, 20 ] ];
// This function break the even weighted edges in
// two parts. Makes the adjacency representation
// of the graph and sends it for two coloring.
if (isOddSum(info, n, m) == true)
document.write("No");
else
document.write("Yes");
</script>
Producción
No
Complejidad de tiempo: O(N*N) , ya que estamos usando un bucle para recorrer N veces y en cada recorrido estamos llamando a la función twoColorUtil que cuesta O(N) tiempo.
Espacio Auxiliar: O(N), ya que estamos usando espacio extra.
Este artículo es una contribución de Parth Trehan . 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.
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