Dada una array arr[][] que consta de N segmentos de la forma {L, R, V} donde, [L, R] denota un segmento con velocidad V en cualquier dirección, la tarea es verificar si es posible asignar direcciones como izquierda o derecha a todos los segmentos de modo que no se crucen después de un largo período de tiempo .
Ejemplos:
Entrada: arr[][] = {{5, 7, 2}, {4, 6, 1}, {1, 5, 2}, {6, 5, 1}}
Salida: Sí
Explicación: Asignar dirección izquierda a los segmentos primero y segundo y dirección derecha a los segmentos tercero y cuarto.Entrada: arr[][] = {{1, 2, 3}}
Salida: Sí
Enfoque: El problema dado se puede resolver con base en las siguientes observaciones:
- Caso 1 : Cuando las velocidades de dos segmentos son diferentes:
- La idea es asignar la misma dirección a ambos segmentos.
- Por lo tanto, después de un largo período de tiempo, los segmentos nunca se cruzarán ni se superpondrán. Es posible que entre este tiempo, en algún lugar, los segmentos se superpongan. Luego, eventualmente un segmento superará al otro.
- Caso 2 : cuando la velocidad de dos segmentos es la misma, pero no se intersecan en t = 0:
- La idea es asignarles la misma dirección de movimiento a ambos segmentos.
- Dado que su posición relativa no cambiará debido a la misma velocidad y la misma dirección, después de un tiempo infinito, sus posiciones relativas seguirán siendo las mismas y no se superpondrán.
- Caso 3 : cuando la velocidad de dos segmentos es la misma y se superponen/intersectan inicialmente.
- La idea es asignarles la dirección opuesta del movimiento.
Los siguientes ejemplos ilustran todos los casos anteriores:
A partir de las observaciones anteriores, la idea es crear un gráfico para todos los segmentos superpuestos y verificar si el gráfico creado es bipartito o no . Si el gráfico creado es bipartito, entonces es posible asignar direcciones a todos los segmentos para que no se crucen después de un largo período de tiempo. Por lo tanto, imprima “Sí” . De lo contrario, escriba “No” .
Siga los pasos a continuación para resolver el problema:
- Genere todos los pares posibles de elementos distintos de la array dada arr[][] . Si algún par de segmentos (arr[i], arr[j]) se superponen, agregue un borde no dirigido (i, j) entre ellos.
- Compruebe si el gráfico dado es bipartito o no para todos los Nodes posibles en el rango [0, N – 1] . Si se encuentra que es cierto, escriba «Sí» . De lo contrario, escriba “No” .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Stores the details of the Segment
struct Node {
int L, R, V;
};
// Function to check whether the
// graph is bipartite or not
bool check(vector<int> Adj[], int Src,
int N, bool visited[])
{
int color[N] = { 0 };
// Mark source node as visited
visited[Src] = true;
queue<int> q;
// Push the source vertex in queue
q.push(Src);
while (!q.empty()) {
// Get the front of the queue
int u = q.front();
q.pop();
// Assign the color
// to the popped node
int Col = color[u];
// Traverse the adjacency
// list of the node u
for (int x : Adj[u]) {
// If any node is visited &
// a different colors has been
// assigned, then return false
if (visited[x] == true
&& color[x] == Col) {
return false;
}
else if (visited[x] == false) {
// Set visited[x]
visited[x] = true;
// Push the node x
// into the queue
q.push(x);
// Update color of node
color[x] = 1 - Col;
}
}
}
// If the graph is bipartite
return true;
}
// Function to add an edge
// between the nodes u and v
void addEdge(vector<int> Adj[],
int u, int v)
{
Adj[u].push_back(v);
Adj[v].push_back(u);
}
// Function to check if the assignment
// of direction can be possible to all
// the segments, such that they do not
// intersect after a long period of time
void isPossible(struct Node Arr[], int N)
{
// Stores the adjacency list
// of the created graph
vector<int> Adj[N];
// Generate all possible pairs
for (int i = 0; i < N - 1; i++) {
for (int j = i + 1; j < N; j++) {
// If segments do not overlap
if (Arr[i].R < Arr[j].L
|| Arr[i].L > Arr[j].R) {
continue;
}
// Otherwise, the segments overlap
else {
if (Arr[i].V == Arr[j].V) {
// If both segments have
// same speed, then add an edge
addEdge(Adj, i, j);
}
}
}
}
// Keep the track of visited nodes
bool visited[N] = { false };
// Iterate for all possible nodes
for (int i = 0; i < N; i++) {
if (visited[i] == false
&& Adj[i].size() > 0) {
// Check whether graph is
// bipartite or not
if (check(Adj, i, N, visited)
== false) {
cout << "No";
return;
}
}
}
// If the graph is bipartite
cout << "Yes";
}
// Driver Code
int main()
{
struct Node arr[] = {
{ 5, 7, 2 }, { 4, 6, 1 },
{ 1, 5, 2 }, { 6, 5, 1 }
};
int N = sizeof(arr) / sizeof(arr[0]);
isPossible(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG{
// Stores the details of the Segment
static class Node
{
int L, R, V;
Node(int L, int R, int V)
{
this.L = L;
this.R = R;
this.V = V;
}
}
// Function to check whether the
// graph is bipartite or not
static boolean check(ArrayList<Integer> Adj[], int Src,
int N, boolean visited[])
{
int color[] = new int[N];
// Mark source node as visited
visited[Src] = true;
ArrayDeque<Integer> q = new ArrayDeque<>();
// Push the source vertex in queue
q.addLast(Src);
while (!q.isEmpty())
{
// Get the front of the queue
int u = q.removeFirst();
// Assign the color
// to the popped node
int Col = color[u];
// Traverse the adjacency
// list of the node u
for(int x : Adj[u])
{
// If any node is visited &
// a different colors has been
// assigned, then return false
if (visited[x] == true && color[x] == Col)
{
return false;
}
else if (visited[x] == false)
{
// Set visited[x]
visited[x] = true;
// Push the node x
// into the queue
q.addLast(x);
// Update color of node
color[x] = 1 - Col;
}
}
}
// If the graph is bipartite
return true;
}
// Function to add an edge
// between the nodes u and v
static void addEdge(ArrayList<Integer> Adj[], int u,
int v)
{
Adj[u].add(v);
Adj[v].add(u);
}
// Function to check if the assignment
// of direction can be possible to all
// the segments, such that they do not
// intersect after a long period of time
static void isPossible(Node Arr[], int N)
{
// Stores the adjacency list
// of the created graph
@SuppressWarnings("unchecked")
ArrayList<Integer> [] Adj = (ArrayList<Integer>[])new ArrayList[N];
// Initialize
for(int i = 0; i < N; i++)
Adj[i] = new ArrayList<>();
// Generate all possible pairs
for(int i = 0; i < N - 1; i++)
{
for(int j = i + 1; j < N; j++)
{
// If segments do not overlap
if (Arr[i].R < Arr[j].L ||
Arr[i].L > Arr[j].R)
{
continue;
}
// Otherwise, the segments overlap
else
{
if (Arr[i].V == Arr[j].V)
{
// If both segments have
// same speed, then add an edge
addEdge(Adj, i, j);
}
}
}
}
// Keep the track of visited nodes
boolean visited[] = new boolean[N];
// Iterate for all possible nodes
for(int i = 0; i < N; i++)
{
if (visited[i] == false && Adj[i].size() > 0)
{
// Check whether graph is
// bipartite or not
if (check(Adj, i, N, visited) == false)
{
System.out.println("No");
return;
}
}
}
// If the graph is bipartite
System.out.println("Yes");
}
// Driver Code
public static void main(String[] args)
{
Node arr[] = { new Node(5, 7, 2), new Node(4, 6, 1),
new Node(1, 5, 2), new Node(6, 5, 1) };
int N = arr.length;
isPossible(arr, N);
}
}
// This code is contributed by Kingash
Python3
# Python3 program for the above approach
from collections import deque
# Function to check whether the
# graph is bipartite or not
def check(Adj, Src, N, visited):
color = [0] * N
# Mark source node as visited
visited = [True] * Src
q = deque()
# Push the source vertex in queue
q.append(Src)
while (len(q) > 0):
# Get the front of the queue
u = q.popleft()
# q.pop()
# Assign the color
# to the popped node
Col = color[u]
# Traverse the adjacency
# list of the node u
for x in Adj[u]:
# If any node is visited &
# a different colors has been
# assigned, then return false
if (visited[x] == True and
color[x] == Col):
return False
elif (visited[x] == False):
# Set visited[x]
visited[x] = True
# Push the node x
# into the queue
q.append(x)
# Update color of node
color[x] = 1 - Col
# If the graph is bipartite
return True
# Function to add an edge
# between the nodes u and v
def addEdge(Adj, u, v):
Adj[u].append(v)
Adj[v].append(u)
return Adj
# Function to check if the assignment
# of direction can be possible to all
# the segments, such that they do not
# intersect after a long period of time
def isPossible(Arr, N):
# Stores the adjacency list
# of the created graph
Adj = [[] for i in range(N)]
# Generate all possible pairs
for i in range(N - 1):
for j in range(i + 1, N):
# If segments do not overlap
if (Arr[i][0] < Arr[j][1] or
Arr[i][1] > Arr[j][0]):
continue
# Otherwise, the segments overlap
else:
if (Arr[i][2] == Arr[j][2]):
# If both segments have
# same speed, then add an edge
Adj = addEdge(Adj, i, j)
# Keep the track of visited nodes
visited = [False] * N
# Iterate for all possible nodes
for i in range(N):
if (visited[i] == False and len(Adj[i]) > 0):
# Check whether graph is
# bipartite or not
if (check(Adj, i, N, visited) == False):
print ("No")
return
# If the graph is bipartite
print ("Yes")
# Driver Code
if __name__ == '__main__':
arr = [ [ 5, 7, 2 ], [ 4, 6, 1 ],
[ 1, 5, 2 ], [ 6, 5, 1 ] ]
N = len(arr)
isPossible(arr, N)
# This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Stores the details of the Segment
class Node
{
public int L, R, V;
};
static Node newNode(int L, int R, int V)
{
Node temp = new Node();
temp.L = L;
temp.R = R;
temp.V = V;
return temp;
}
// Function to check whether the
// graph is bipartite or not
static bool check(List<int> []Adj, int Src,
int N, bool []visited)
{
int []color = new int[N];
// Mark source node as visited
visited[Src] = true;
Queue<int> q = new Queue<int>();
// Push the source vertex in queue
q.Enqueue(Src);
while (q.Count > 0)
{
// Get the front of the queue
int u = q.Peek();
q.Dequeue();
// Assign the color
// to the popped node
int Col = color[u];
// Traverse the adjacency
// list of the node u
foreach (int x in Adj[u])
{
// If any node is visited &
// a different colors has been
// assigned, then return false
if (visited[x] == true &&
color[x] == Col)
{
return false;
}
else if (visited[x] == false)
{
// Set visited[x]
visited[x] = true;
// Push the node x
// into the queue
q.Enqueue(x);
// Update color of node
color[x] = 1 - Col;
}
}
}
// If the graph is bipartite
return true;
}
// Function to add an edge
// between the nodes u and v
static void addEdge(List<int> []Adj, int u, int v)
{
Adj[u].Add(v);
Adj[v].Add(u);
}
// Function to check if the assignment
// of direction can be possible to all
// the segments, such that they do not
// intersect after a long period of time
static void isPossible(Node []Arr, int N)
{
// Stores the adjacency list
// of the created graph
List<int> [] Adj = new List<int>[N];
// Initialize
for(int i = 0; i < N; i++)
Adj[i] = new List<int>();
// Generate all possible pairs
for(int i = 0; i < N - 1; i++)
{
for(int j = i + 1; j < N; j++)
{
// If segments do not overlap
if (Arr[i].R < Arr[j].L ||
Arr[i].L > Arr[j].R)
{
continue;
}
// Otherwise, the segments overlap
else
{
if (Arr[i].V == Arr[j].V)
{
// If both segments have
// same speed, then add an edge
addEdge(Adj, i, j);
}
}
}
}
// Keep the track of visited nodes
bool []visited = new bool[N];
// Iterate for all possible nodes
for(int i = 0; i < N; i++)
{
if (visited[i] == false && Adj[i].Count > 0)
{
// Check whether graph is
// bipartite or not
if (check(Adj, i, N, visited) == false)
{
Console.Write("No");
return;
}
}
}
// If the graph is bipartite
Console.Write("Yes");
}
// Driver Code
public static void Main()
{
Node []arr = { newNode(5, 7, 2), newNode(4, 6, 1),
newNode(1, 5, 2), newNode(6, 5, 1) };
int N = arr.Length;
isPossible(arr, N);
}
}
// This code is contributed by SURENDRA_GANGWAR
Javascript
<script>
// JavaScript program for the above approach
// Stores the details of the Segment
class Node
{
constructor(L,R,V)
{
this.L = L;
this.R = R;
this.V = V;
}
}
// Function to check whether the
// graph is bipartite or not
function check(Adj,Src,N,visited)
{
let color = new Array(N);
// Mark source node as visited
visited[Src] = true;
let q = [];
// Push the source vertex in queue
q.push(Src);
while (q.length!=0)
{
// Get the front of the queue
let u = q.shift();
// Assign the color
// to the popped node
let Col = color[u];
// Traverse the adjacency
// list of the node u
for(let x=0;x< Adj[u].length;x++)
{
// If any node is visited &
// a different colors has been
// assigned, then return false
if (visited[Adj[u][x]] == true && color[Adj[u][x]] == Col)
{
return false;
}
else if (visited[Adj[u][x]] == false)
{
// Set visited[x]
visited[Adj[u][x]] = true;
// Push the node x
// into the queue
q.push(Adj[u][x]);
// Update color of node
color[Adj[u][x]] = 1 - Col;
}
}
}
// If the graph is bipartite
return true;
}
// Function to add an edge
// between the nodes u and v
function addEdge(Adj,u,v)
{
Adj[u].push(v);
Adj[v].push(u);
}
// Function to check if the assignment
// of direction can be possible to all
// the segments, such that they do not
// intersect after a long period of time
function isPossible(Arr,N)
{
// Stores the adjacency list
// of the created graph
let Adj = new Array(N);
// Initialize
for(let i = 0; i < N; i++)
Adj[i] = [];
// Generate all possible pairs
for(let i = 0; i < N - 1; i++)
{
for(let j = i + 1; j < N; j++)
{
// If segments do not overlap
if (Arr[i].R < Arr[j].L ||
Arr[i].L > Arr[j].R)
{
continue;
}
// Otherwise, the segments overlap
else
{
if (Arr[i].V == Arr[j].V)
{
// If both segments have
// same speed, then add an edge
addEdge(Adj, i, j);
}
}
}
}
// Keep the track of visited nodes
let visited = new Array(N);
for(let i=0;i<N;i++)
visited[i]=false;
// Iterate for all possible nodes
for(let i = 0; i < N; i++)
{
if (visited[i] == false && Adj[i].length > 0)
{
// Check whether graph is
// bipartite or not
if (check(Adj, i, N, visited) == false)
{
document.write("No<bR>");
return;
}
}
}
// If the graph is bipartite
document.write("Yes<br>");
}
// Driver Code
let arr=[new Node(5, 7, 2), new Node(4, 6, 1),
new Node(1, 5, 2), new Node(6, 5, 1)];
let N = arr.length;
isPossible(arr, N);
// This code is contributed by patel2127
</script>
Producción:
Yes
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N 2 )
Publicación traducida automáticamente
Artículo escrito por prakersh009 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA