Dado un gráfico no dirigido con N vértices y M aristas y sin bucles propios ni aristas múltiples. La tarea es convertir el gráfico no dirigido dado en un gráfico dirigido de modo que no haya un camino de longitud mayor que 1. Si es posible hacer tal gráfico, imprima dos enteros separados por espacios u y v en M líneas donde u, v denota vértices de origen y destino respectivamente. Si no es posible, imprima -1. Ejemplos:
Entrada:
Salida: 1 2 1 3 1 4
Entrada:
Salida: -1 Para el gráfico dado no es posible obtener un gráfico dirigido tal que no haya camino de longitud mayor que 1
Enfoque: supongamos que el gráfico contiene un ciclo de longitud impar. Significa que unas dos aristas consecutivas de este ciclo estarán orientadas de la misma manera y formarán un camino de longitud dos. Entonces la respuesta es -1. Y si el gráfico no contiene ciclos de longitud impar. Entonces es bipartito . Vamos a colorearlo y ver qué tenemos. Obtuvimos algunos vértices en la parte izquierda, algunos vértices en la parte derecha y todos los bordes conectando vértices de diferentes partes. Orientemos todos los bordes de manera que vayan de la parte izquierda a la parte derecha. A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define N 100005
// To store the graph
vector<int> gr[N];
// To store colour of each vertex
int colour[N];
// To store edges
vector<pair<int, int> > edges;
// To check graph is bipartite or not
bool bip;
// Function to add edges
void add_edge(int x, int y)
{
gr[x].push_back(y);
gr[y].push_back(x);
edges.push_back(make_pair(x, y));
}
// Function to check given graph
// is bipartite or not
void dfs(int x, int col)
{
// colour the vertex x
colour[x] = col;
// For all it's child vertices
for (auto i : gr[x]) {
// If still not visited
if (colour[i] == -1)
dfs(i, col ^ 1);
// If visited and having
// same colour as parent
else if (colour[i] == col)
bip = false;
}
}
// Function to convert the undirected
// graph into the directed graph such that
// there is no path of length greater than 1
void Directed_Graph(int n, int m)
{
// Initially each vertex has no colour
memset(colour, -1, sizeof colour);
// Suppose bipartite is possible
bip = true;
// Call bipartite function
dfs(1, 1);
// If bipartite is not possible
if (!bip) {
cout << -1;
return;
}
// If bipartite is possible
for (int i = 0; i < m; i++) {
// Make an edge from vertex having
// colour 1 to colour 0
if (colour[edges[i].first] == 0)
swap(edges[i].first, edges[i].second);
cout << edges[i].first << " "
<< edges[i].second << endl;
}
}
// Driver code
int main()
{
int n = 4, m = 3;
// Add edges
add_edge(1, 2);
add_edge(1, 3);
add_edge(1, 4);
// Function call
Directed_Graph(n, m);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
static class pair
{
int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
static int N = 100005;
// To store the graph
static Vector<Integer> []gr = new Vector[N];
// To store colour of each vertex
static int []colour = new int[N];
// To store edges
static Vector<pair> edges = new Vector<>();
// To check graph is bipartite or not
static boolean bip;
// Function to add edges
static void add_edge(int x, int y)
{
gr[x].add(y);
gr[y].add(x);
edges.add(new pair(x, y));
}
// Function to check given graph
// is bipartite or not
static void dfs(int x, int col)
{
// colour the vertex x
colour[x] = col;
// For all it's child vertices
for (Integer i : gr[x])
{
// If still not visited
if (colour[i] == -1)
dfs(i, col ^ 1);
// If visited and having
// same colour as parent
else if (colour[i] == col)
bip = false;
}
}
// Function to convert the undirected
// graph into the directed graph such that
// there is no path of length greater than 1
static void Directed_Graph(int n, int m)
{
// Initially each vertex has no colour
for (int i = 0; i < N; i++)
colour[i] = -1;
// Suppose bipartite is possible
bip = true;
// Call bipartite function
dfs(1, 1);
// If bipartite is not possible
if (!bip)
{
System.out.print(-1);
return;
}
// If bipartite is possible
for (int i = 0; i < m; i++)
{
// Make an edge from vertex having
// colour 1 to colour 0
if (colour[edges.get(i).first] == 0)
{
Collections.swap(edges, edges.get(i).first,
edges.get(i).second);
}
System.out.println(edges.get(i).first + " " +
edges.get(i).second);
}
}
// Driver code
public static void main(String[] args)
{
int n = 4, m = 3;
for (int i = 0; i < N; i++)
gr[i] = new Vector<>();
// Add edges
add_edge(1, 2);
add_edge(1, 3);
add_edge(1, 4);
// Function call
Directed_Graph(n, m);
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 implementation of the approach N = 100005 # To store the graph gr = [[] for i in range(N)] # To store colour of each vertex colour = [-1] * N # To store edges edges = [] # To check graph is bipartite or not bip = True # Function to add edges def add_edge(x, y): gr[x].append(y) gr[y].append(x) edges.append((x, y)) # Function to check given graph # is bipartite or not def dfs(x, col): # colour the vertex x colour[x] = col global bip # For all it's child vertices for i in gr[x]: # If still not visited if colour[i] == -1: dfs(i, col ^ 1) # If visited and having # same colour as parent elif colour[i] == col: bip = False # Function to convert the undirected # graph into the directed graph such that # there is no path of length greater than 1 def Directed_Graph(n, m): # Call bipartite function dfs(1, 1) # If bipartite is not possible if not bip: print(-1) return # If bipartite is possible for i in range(0, m): # Make an edge from vertex # having colour 1 to colour 0 if colour[edges[i][0]] == 0: edges[i][0], edges[i][1] = edges[i][1], edges[i][0] print(edges[i][0], edges[i][1]) # Driver code if __name__ == "__main__": n, m = 4, 3 # Add edges add_edge(1, 2) add_edge(1, 3) add_edge(1, 4) # Function call Directed_Graph(n, m) # This code is contributed by Rituraj Jain
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG
{
class pair
{
public int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
static int N = 100005;
// To store the graph
static List<int> []gr = new List<int>[N];
// To store colour of each vertex
static int []colour = new int[N];
// To store edges
static List<pair> edges = new List<pair>();
// To check graph is bipartite or not
static Boolean bip;
// Function to add edges
static void add_edge(int x, int y)
{
gr[x].Add(y);
gr[y].Add(x);
edges.Add(new pair(x, y));
}
// Function to check given graph
// is bipartite or not
static void dfs(int x, int col)
{
// colour the vertex x
colour[x] = col;
// For all it's child vertices
foreach (int i in gr[x])
{
// If still not visited
if (colour[i] == -1)
dfs(i, col ^ 1);
// If visited and having
// same colour as parent
else if (colour[i] == col)
bip = false;
}
}
// Function to convert the undirected
// graph into the directed graph such that
// there is no path of length greater than 1
static void Directed_Graph(int n, int m)
{
// Initially each vertex has no colour
for (int i = 0; i < N; i++)
colour[i] = -1;
// Suppose bipartite is possible
bip = true;
// Call bipartite function
dfs(1, 1);
// If bipartite is not possible
if (!bip)
{
Console.Write(-1);
return;
}
// If bipartite is possible
for (int i = 0; i < m; i++)
{
// Make an edge from vertex having
// colour 1 to colour 0
if (colour[edges[i].first] == 0)
{
var v = edges[i].first;
edges[i].first = edges[i].second;
edges[i].second = v;
}
Console.WriteLine(edges[i].first + " " +
edges[i].second);
}
}
// Driver code
public static void Main(String[] args)
{
int n = 4, m = 3;
for (int i = 0; i < N; i++)
gr[i] = new List<int>();
// Add edges
add_edge(1, 2);
add_edge(1, 3);
add_edge(1, 4);
// Function call
Directed_Graph(n, m);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript code to implement the above approach
// Python3 implementation of the approach
let N = 100005
// To store the graph
let gr = new Array(N);
for(let i = 0; i < N; i++){
gr[i] = new Array()
}
// To store colour of each vertex
let colour = new Array(N).fill(-1)
// To store edges
let edges = []
// To check graph is bipartite or not
let bip = true
// Function to add edges
function add_edge(x, y){
gr[x].push(y)
gr[y].push(x)
edges.push([x, y])
}
// Function to check given graph
// is bipartite or not
function dfs(x, col){
// colour the vertex x
colour[x] = col
// For all it's child vertices
for(let i of gr[x]){
// If still not visited
if(colour[i] == -1)
dfs(i, col ^ 1)
// If visited and having
// same colour as parent
else if(colour[i] == col)
bip = false
}
}
// Function to convert the undirected
// graph into the directed graph such that
// there is no path of length greater than 1
function Directed_Graph(n, m){
// Call bipartite function
dfs(1, 1)
// If bipartite is not possible
if(bip == 0){
document.write(-1,"</br>")
return
}
// If bipartite is possible
for(let i=0;i<m;i++){
// Make an edge from vertex
// having colour 1 to colour 0
if(colour[edges[i][0]] == 0){
let temp = edges[i][0]
edges[i][0] = edges[i][1]
edges[i][1] = temp
}
document.write(edges[i][0], edges[i][1],"</br>")
}
}
// Driver code
let n =4, m = 3
// Add edges
add_edge(1, 2)
add_edge(1, 3)
add_edge(1, 4)
// Function call
Directed_Graph(n, m)
// This code is contributed by shinjanpatra
</script>
Producción:
1 2 1 3 1 4
Publicación traducida automáticamente
Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA