Dado un gráfico ponderado dirigido con N vértices y M aristas y una arista (U, V) . La tarea es encontrar si hay un camino alternativo presente de U a V con un peso individual de los bordes en el camino alternativo menor que el peso del camino directo. Si está presente, escriba Sí , de lo contrario, escriba No.
Ejemplos
Para el gráfico dirigido dado:
Entrada: N = 7, M = 10, U = 3, V = 6.
Salida: No
Explicación:
Para el borde dado {3, 6}, peso = 16. No hay un camino alternativo para llegar a 6 desde 3. Por lo tanto, el la respuesta es noEntrada: N = 7, M = 10, U = 1, V = 6.
Salida: Sí
Explicación:
=> Para el borde dado {1, 6}, peso = 5.
=> Camino alternativo para llegar a 6 desde 1 = { 1, 5, 6} con pesos individuales {12, 2} que es mayor que 5. Por lo tanto, no se puede considerar este camino.
=> Camino alternativo para llegar a 6 desde 1 = {1, 2, 4, 5, 6} con pesos individuales {5, 1, 1, 2} que no es menor que 5. Por lo tanto, este camino no se puede considerar.
=> Camino alternativo para llegar a 6 desde 1 = {1, 4, 5, 6} con pesos individuales {3, 1, 2} que es menor que 5. Por lo tanto, se puede considerar este camino.
=> Por lo tanto, la respuesta es Sí
Acercarse:
- Atraviese el gráfico dirigido dado con el vértice inicial U utilizando la búsqueda primero en profundidad (DFS) Traversal .
- Durante DFS Traversal , si el peso de cualquier borde es mayor que el borde dirigido, entonces esa ruta no se incluye.
- Si alcanzamos el vértice V con el peso de cada borde en la ruta transversal menor que el borde dirigido, entonces existe una ruta alternativa.
- De lo contrario, no hay camino entre el vértice U y el vértice V que no sea el camino directo.
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
// Edge class
class Edge
{
public:
int u;
int v;
int w;
// Edge constructor to
// initialize edge (u, v) with
// weight w
Edge(int u, int v, int w)
{
this->u = u;
this->v = v;
this->w = w;
}
};
class GFG{
public:
// Array to mark already
// visited vertices
bool *visited;
// Adjacency list representation
// of the graph
vector<Edge *> *graph;
// GfG class constructor
GFG(int size)
{
visited = new bool[size];
graph = new vector<Edge *>[size];
}
// Depth First Search to traverse
// all vertices with weight less
// than weight of the dfs root
void dfs(int S, int W)
{
// Marking the vertex visited
visited[S] = true;
// Traversing adjacent vertex
for(Edge *uv : graph[S])
{
int ver = uv->v;
int w = uv->w;
if (!visited[ver] && w < W)
dfs(ver, W);
}
}
};
// Driver code
int main()
{
// Number of vertices
int N = 7;
// Number of edges
int M = 10;
// Edge to be checked
int U_V[] = {3, 6};
// Creating GfG object
GFG *obj = new GFG(8);
// Creating edges
Edge *e0 = new Edge(1, 2, 5);
Edge *e1 = new Edge(1, 4, 3);
Edge *e2 = new Edge(1, 5, 12);
Edge *e3 = new Edge(1, 6, 5);
Edge *e4 = new Edge(4, 5, 1);
Edge *e5 = new Edge(5, 6, 2);
Edge *e6 = new Edge(5, 3, 1);
Edge *e7 = new Edge(3, 6, 16);
Edge *e8 = new Edge(4, 7, 1);
Edge *e9 = new Edge(2, 4, 1);
// Adding edges to the graph
obj->graph[1].push_back(e0);
obj->graph[1].push_back(e1);
obj->graph[1].push_back(e2);
obj->graph[1].push_back(e3);
obj->graph[4].push_back(e4);
obj->graph[5].push_back(e5);
obj->graph[5].push_back(e6);
obj->graph[3].push_back(e7);
obj->graph[4].push_back(e8);
obj->graph[2].push_back(e9);
// DFS traversal from
// vertex U
obj->dfs(U_V[0], 16);
// If there is alternate
// path then print YES,
// else NO
if (obj->visited[U_V[1]])
{
cout << "NO" << endl;
}
else
{
cout << "YES" << endl;
}
}
// This code is contributed by sanjeev2552
Java
// Java program for above approach
import java.util.*;
// To ignore the unchecked warning
@SuppressWarnings("unchecked")
// GfG class
public class GfG {
// Array to mark already
// visited vertices
static private boolean visited[];
// Adjacency list representation
// of the graph
static private ArrayList<Edge> graph[];
// GfG class constructor
public GfG(int size)
{
visited = new boolean[size];
graph = new ArrayList[size];
}
// Edge class
static class Edge {
int u;
int v;
int w;
// Edge constructor to
// initialize edge (u, v) with
// weight w
Edge(int u, int v, int w)
{
this.u = u;
this.v = v;
this.w = w;
}
}
// Helper method to
// initialize graph
static private void helperInitialize(int size)
{
for (int i = 0; i < size; i++) {
graph[i] = new ArrayList<Edge>();
}
}
// Depth First Search to traverse
// all vertices with weight less
// than weight of the dfs root
static private void dfs(int S, int W)
{
// Marking the vertex visited
visited[S] = true;
// Traversing adjacent vertex
for (Edge uv : graph[S]) {
int ver = uv.v;
int w = uv.w;
if (!visited[ver] && w < W)
dfs(ver, W);
}
}
// Driver function
public static void main(String[] args)
{
// Number of vertices
int N = 7;
// Number of edges
int M = 10;
// Edge to be checked
int U_V[] = { 3, 6 };
// Creating GfG object
GfG obj = new GfG(8);
// Initializing graph
helperInitialize(8);
// Creating edges
Edge e0 = new Edge(1, 2, 5);
Edge e1 = new Edge(1, 4, 3);
Edge e2 = new Edge(1, 5, 12);
Edge e3 = new Edge(1, 6, 5);
Edge e4 = new Edge(4, 5, 1);
Edge e5 = new Edge(5, 6, 2);
Edge e6 = new Edge(5, 3, 1);
Edge e7 = new Edge(3, 6, 16);
Edge e8 = new Edge(4, 7, 1);
Edge e9 = new Edge(2, 4, 1);
// Adding edges to the graph
graph[1].add(e0);
graph[1].add(e1);
graph[1].add(e2);
graph[1].add(e3);
graph[4].add(e4);
graph[5].add(e5);
graph[5].add(e6);
graph[3].add(e7);
graph[4].add(e8);
graph[2].add(e9);
// DFS traversal from
// vertex U
dfs(U_V[0], 16);
// If there is alternate
// path then print YES,
// else NO
if (visited[U_V[1]]) {
System.out.print("No");
}
else {
System.out.print("Yes");
}
}
}
Python3
# Python3 program for above approach
class Edge:
# Edge constructor to
# initialize edge (u, v) with
# weight w
def __init__(self, u, v, w):
self.u = u
self.v = v
self.w = w
# Depth First Search to traverse
# all vertices with weight less
# than weight of the dfs root
def dfs(S, W):
global visited,graph
# Marking the vertex visited
visited[S] = True
# Traversing adjacent vertex
for uv in graph[S]:
ver = uv.v
w = uv.w
if (not visited[ver] and w < W):
dfs(ver, W)
# Driver code
if __name__ == '__main__':
# Number of vertices
N = 7
# Number of edges
M = 10
# Edge to be checked
U_V = [3, 6]
# Creating GfG object
visited, graph = [False for i in range(8)], [[] for i in range(8)]
# Creating edges
e0 = Edge(1, 2, 5)
e1 = Edge(1, 4, 3)
e2 = Edge(1, 5, 12)
e3 = Edge(1, 6, 5)
e4 = Edge(4, 5, 1)
e5 = Edge(5, 6, 2)
e6 = Edge(5, 3, 1)
e7 = Edge(3, 6, 16)
e8 = Edge(4, 7, 1)
e9 = Edge(2, 4, 1)
# Adding edges to the graph
graph[1].append(e0)
graph[1].append(e1)
graph[1].append(e2)
graph[1].append(e3)
graph[4].append(e4)
graph[5].append(e5)
graph[5].append(e6)
graph[3].append(e7)
graph[4].append(e8)
graph[2].append(e9)
# DFS traversal from
# vertex U
dfs(U_V[0], 16)
# If there is alternate
# path then print YES,
# else NO
if (visited[U_V[1]]):
print("NO")
else :
print("YES")
# This code is contributed by mohit kumar 29
C#
// C# program for above approach
using System;
using System.Collections.Generic;
// GfG class
class GfG
{
// Array to mark already
// visited vertices
static private bool []visited;
// Adjacency list representation
// of the graph
static private List<Edge> []graph;
// GfG class constructor
public GfG(int size)
{
visited = new bool[size];
graph = new List<Edge>[size];
}
// Edge class
class Edge
{
public int u;
public int v;
public int w;
// Edge constructor to
// initialize edge (u, v) with
// weight w
public Edge(int u, int v, int w)
{
this.u = u;
this.v = v;
this.w = w;
}
}
// Helper method to
// initialize graph
static private void helperInitialize(int size)
{
for (int i = 0; i < size; i++)
{
graph[i] = new List<Edge>();
}
}
// Depth First Search to traverse
// all vertices with weight less
// than weight of the dfs root
static private void dfs(int S, int W)
{
// Marking the vertex visited
visited[S] = true;
// Traversing adjacent vertex
foreach (Edge uv in graph[S])
{
int ver = uv.v;
int w = uv.w;
if (!visited[ver] && w < W)
dfs(ver, W);
}
}
// Driver function
public static void Main(String[] args)
{
// Edge to be checked
int []U_V = { 3, 6 };
// Creating GfG object
GfG obj = new GfG(8);
// Initializing graph
helperInitialize(8);
// Creating edges
Edge e0 = new Edge(1, 2, 5);
Edge e1 = new Edge(1, 4, 3);
Edge e2 = new Edge(1, 5, 12);
Edge e3 = new Edge(1, 6, 5);
Edge e4 = new Edge(4, 5, 1);
Edge e5 = new Edge(5, 6, 2);
Edge e6 = new Edge(5, 3, 1);
Edge e7 = new Edge(3, 6, 16);
Edge e8 = new Edge(4, 7, 1);
Edge e9 = new Edge(2, 4, 1);
// Adding edges to the graph
graph[1].Add(e0);
graph[1].Add(e1);
graph[1].Add(e2);
graph[1].Add(e3);
graph[4].Add(e4);
graph[5].Add(e5);
graph[5].Add(e6);
graph[3].Add(e7);
graph[4].Add(e8);
graph[2].Add(e9);
// DFS traversal from
// vertex U
dfs(U_V[0], 16);
// If there is alternate
// path then print YES,
// else NO
if (visited[U_V[1]])
{
Console.Write("No");
}
else
{
Console.Write("Yes");
}
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program for above approach
// Array to mark already
// visited vertices
let visited = new Array(100);
// Adjacency list representation
// of the graph
let graph=new Array(100);
// Edge class
class Edge
{
constructor(u,v,w)
{
this.u = u;
this.v = v;
this.w = w;
}
}
// Helper method to
// initialize graph
function helperInitialize(size)
{
for (let i = 0; i < size; i++) {
graph[i] = [];
}
}
// Depth First Search to traverse
// all vertices with weight less
// than weight of the dfs root
function dfs(S,W)
{
// Marking the vertex visited
visited[S] = true;
// Traversing adjacent vertex
for (let uv=0;uv<graph[S].length;uv++) {
let ver = graph[S][uv].v;
let w = graph[S][uv].w;
if (!visited[ver] && w < W)
dfs(ver, W);
}
}
// Driver function
// Number of vertices
let N = 7;
// Number of edges
let M = 10;
// Edge to be checked
let U_V = [ 3, 6 ];
// Initializing graph
helperInitialize(8);
// Creating edges
let e0 = new Edge(1, 2, 5);
let e1 = new Edge(1, 4, 3);
let e2 = new Edge(1, 5, 12);
let e3 = new Edge(1, 6, 5);
let e4 = new Edge(4, 5, 1);
let e5 = new Edge(5, 6, 2);
let e6 = new Edge(5, 3, 1);
let e7 = new Edge(3, 6, 16);
let e8 = new Edge(4, 7, 1);
let e9 = new Edge(2, 4, 1);
// Adding edges to the graph
graph[1].push(e0);
graph[1].push(e1);
graph[1].push(e2);
graph[1].push(e3);
graph[4].push(e4);
graph[5].push(e5);
graph[5].push(e6);
graph[3].push(e7);
graph[4].push(e8);
graph[2].push(e9);
// DFS traversal from
// vertex U
dfs(U_V[0], 16);
// If there is alternate
// path then print YES,
// else NO
if (visited[U_V[1]]) {
document.write("No");
}
else {
document.write("Yes");
}
// This code is contributed by unknown2108
</script>
Producción:
Yes
Complejidad temporal: O(N + M), donde N = número de vértices y M = número de aristas.
Publicación traducida automáticamente
Artículo escrito por ishan_trivedi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA