Dado un gráfico que tiene N+1 Nodes con 2*N-1 aristas y una array booleana arr[ ] , la tarea es encontrar si se pueden visitar todos los Nodes exactamente una vez e imprimir cualquier ruta posible. También se sabe que los bordes N-1 van i-th a (i+1)-ésimo Node y los bordes restantes van i-th a (n+1)-th Node si arr[i] es 0 de lo contrario (n+1) -th a i-th .
Ejemplos:
Entrada: N = 3, arr = {0, 1, 0}
Salida: [1, 2, 3, 4]
Explicación:
a partir de los datos dados, los bordes serán:
1 -> 2
2 -> 3
1 -> 4
4 -> 2
3 -> 4Por lo tanto, uno puede seguir el camino: 1 -> 2 -> 3 -> 4
Entrada: N = 4, array = {0, 1, 1, 1}
Salida: [1, 4, 2, 3]
Enfoque: este problema se puede resolver utilizando un enfoque codicioso con algunas observaciones. Las observaciones se dan a continuación:
- Si arr[1] es 1 , siga la ruta [N+1 -> 1 -> 2……..-> N] .
- Si arr[N] es 0 , siga la ruta [1 -> 2 ->……….-> N -> N+1] .
- Si arr[1] es 0 y arr[N] es 1 , debe existir un entero i (1 ≤ i< N) donde arr[i] =0 y arr[i+1] = 1 , entonces el camino [1 -> 2 -> ⋯ -> i -> N+1 -> i+1 -> i+2 -> ⋯N] es válido.
- El paso anterior demuestra que siempre existe un camino hamiltoniano en este gráfico.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for above approach.
#include <bits/stdc++.h>
using namespace std;
// Function to find print path
void findpath(int N, int a[])
{
// If a[0] is 1
if (a[0]) {
// Printing path
cout <<" "<< N + 1;
for (int i = 1; i <= N; i++)
cout <<" " << i;
return;
}
// Seeking for a[i] = 0 and a[i+1] = 1
for (int i = 0; i < N - 1; i++) {
if (!a[i] && a[i + 1]) {
// Printing path
for (int j = 1; j <= i; j++)
cout <<" "<< j;
cout <<" "<< N + 1;
for (int j = i + 1; j <= N; j++)
cout <<" "<< j;
return;
}
}
// If a[N-1] = 0
for (int i = 1; i <= N; i++)
cout <<" "<< i;
cout <<" "<< N + 1;
}
// Driver Code
int main()
{
// Given Input
int N = 3, arr[] = { 0, 1, 0 };
// Function Call
findpath(N, arr);
}
// This code is contributed by shivanisinghss2110
C
// C++ program for above approach.
#include <bits/stdc++.h>
using namespace std;
// Function to find print path
void findpath(int N, int a[])
{
// If a[0] is 1
if (a[0]) {
// Printing path
printf("%d ", N + 1);
for (int i = 1; i <= N; i++)
printf("%d ", i);
return;
}
// Seeking for a[i] = 0 and a[i+1] = 1
for (int i = 0; i < N - 1; i++) {
if (!a[i] && a[i + 1]) {
// Printing path
for (int j = 1; j <= i; j++)
printf("%d ", j);
printf("%d ", N + 1);
for (int j = i + 1; j <= N; j++)
printf("%d ", j);
return;
}
}
// If a[N-1] = 0
for (int i = 1; i <= N; i++)
printf("%d ", i);
printf("%d ", N + 1);
}
// Driver Code
int main()
{
// Given Input
int N = 3, arr[] = { 0, 1, 0 };
// Function Call
findpath(N, arr);
}
Java
// Java program for the above approach
import java.io.*;
class GFG {
// Function to find print path
static void findpath(int N, int a[])
{
// If a[0] is 1
if (a[0] == 1) {
// Printing path
System.out.print((N + 1) + " ");
for (int i = 1; i <= N; i++)
System.out.print((i) + " ");
return;
}
// Seeking for a[i] = 0 and a[i+1] = 1
for (int i = 0; i < N - 1; i++) {
if (a[i] == 0 && a[i + 1] == 1) {
// Printing path
for (int j = 1; j <= i; j++)
System.out.print((j) + " ");
System.out.print((N + 1) + " ");
for (int j = i + 1; j <= N; j++)
System.out.print((j) + " ");
return;
}
}
// If a[N-1] = 0
for (int i = 1; i <= N; i++)
System.out.print((i) + " ");
System.out.print((N + 1) + " ");
}
// Driver Code
public static void main(String[] args)
{
int N = 3, arr[] = { 0, 1, 0 };
// Function Call
findpath(N, arr);
}
}
// This code is contributed by dwivediyash
Python3
# Python 3 program for above approach. # Function to find print path def findpath(N, a): # If a[0] is 1 if (a[0]): # Printing path print(N + 1) for i in range(1,N+1,1): print(i,end = " ") return # Seeking for a[i] = 0 and a[i+1] = 1 for i in range(N - 1): if (a[i]==0 and a[i + 1]): # Printing path for j in range(1,i+1,1): print(j,end = " ") print(N + 1,end = " "); for j in range(i + 1,N+1,1): print(j,end = " ") return # If a[N-1] = 0 for i in range(1,N+1,1): print(i,end = " ") print(N + 1,end = " ") # Driver Code if __name__ == '__main__': # Given Input N = 3 arr = [0, 1, 0] # Function Call findpath(N, arr) # This code is contributed by ipg2016107.
C#
// C# program for above approach.
using System;
class GFG{
// Function to find print path
static void findpath(int N, int []a)
{
// If a[0] is 1
if (a[0]!=0) {
// Printing path
Console.Write(N + 1);
for (int i = 1; i <= N; i++)
Console.Write(i+ " ");
return;
}
// Seeking for a[i] = 0 and a[i+1] = 1
for (int i = 0; i < N - 1; i++) {
if (a[i]==0 && a[i + 1] !=0) {
// Printing path
for (int j = 1; j <= i; j++)
Console.Write(j+" ");
Console.Write(N + 1 + " ");
for (int j = i + 1; j <= N; j++)
Console.Write(j + " ");
return;
}
}
// If a[N-1] = 0
for (int i = 1; i <= N; i++)
Console.Write(i+" ");
Console.Write(N + 1 + " ");
}
// Driver Code
public static void Main()
{
// Given Input
int N = 3;
int []arr = { 0, 1, 0 };
// Function Call
findpath(N, arr);
}
}
// This code is contributed by SURENDRA_GANGWAR.
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to find print path
function findpath(N, a) {
// If a[0] is 1
if (a[0]) {
// Printing path
document.write(N + 1);
for (let i = 1; i <= N; i++)
document.write(i);
return;
}
// Seeking for a[i] = 0 and a[i+1] = 1
for (let i = 0; i < N - 1; i++) {
if (!a[i] && a[i + 1]) {
// Printing path
for (let j = 1; j <= i; j++)
document.write(j+" ");
document.write(N + 1+" ");
for (let j = i + 1; j <= N; j++)
document.write(j+" ");
return;
}
}
// If a[N-1] = 0
for (let i = 1; i <= N; i++)
document.write(i+" ");
document.write(N + 1+" ");
}
// Driver Code
// Given Input
let N = 3, arr = [0, 1, 0];
// Function Call
findpath(N, arr);
// This code is contributed by Potta Lokesh
</script>
Producción:
4 1 2 3
Complejidad temporal: O(N)
Espacio auxiliar: O(1)