Dada una array arr[] de enteros, la tarea es organizar los elementos de la array de manera que el último dígito de un elemento sea igual al primer dígito del siguiente elemento.
Ejemplos:
Entrada: arr[] = {123, 321}
Salida: 123 321Entrada: arr[] = {451, 378, 123, 1254}
Salida: 1254 451 123 378
Enfoque ingenuo: encuentre todas las permutaciones de los elementos de la array y luego imprima la array ordenada que cumpla con la condición requerida. La complejidad temporal de este enfoque es O(N!)
Enfoque eficiente: Cree un gráfico dirigido donde habrá un borde dirigido desde un Node A hasta un Node B si el último dígito del número representado por el Node A es igual al primer dígito del número representado por el Node B. Ahora, encuentra el camino Euleriano para el grafo formado. La complejidad del algoritmo anterior es O(E * E) donde E es el número de aristas en el gráfico.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// To store the array elements
vector<string> arr;
// Adjacency list for the graph nodes
vector<vector<int> > graph;
// To store the euler path
vector<string> path;
// Print eulerian path
bool print_euler(int i, int visited[], int count)
{
// Mark node as visited
// and increase the count
visited[i] = 1;
count++;
// If all the nodes are visited
// then we have traversed the euler path
if (count == graph.size()) {
path.push_back(arr[i]);
return true;
}
// Check if the node lies in euler path
bool b = false;
// Traverse through remaining edges
for (int j = 0; j < graph[i].size(); j++)
if (visited[graph[i][j]] == 0) {
b |= print_euler(graph[i][j], visited, count);
}
// If the euler path is found
if (b) {
path.push_back(arr[i]);
return true;
}
// Else unmark the node
else {
visited[i] = 0;
count--;
return false;
}
}
// Function to create the graph and
// print the required path
void connect()
{
int n = arr.size();
graph.clear();
graph.resize(n);
// Connect the nodes
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j)
continue;
// If the last character matches with the
// first character
if (arr[i][arr[i].length() - 1] == arr[j][0]) {
graph[i].push_back(j);
}
}
}
// Print the path
for (int i = 0; i < n; i++) {
int visited[n] = { 0 }, count = 0;
// If the euler path starts
// from the ith node
if (print_euler(i, visited, count))
break;
}
// Print the euler path
for (int i = path.size() - 1; i >= 0; i--) {
cout << path[i];
if (i != 0)
cout << " ";
}
}
// Driver code
int main()
{
arr.push_back("451");
arr.push_back("378");
arr.push_back("123");
arr.push_back("1254");
// Create graph and print the path
connect();
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG{
// To store the array elements
static List<String> arr = new ArrayList<String>();
// Adjacency list for the graph nodes
static List<List<Integer>> graph = new ArrayList<List<Integer>>();
// To store the euler path
static List<String> path = new ArrayList<String>();
// Print eulerian path
static boolean print_euler(int i, int []visited,
int count)
{
// Mark node as visited
// and increase the count
visited[i] = 1;
count++;
// If all the nodes are visited
// then we have traversed the euler path
if (count == graph.size())
{
path.add(arr.get(i));
return true;
}
// Check if the node lies in euler path
boolean b = false;
// Traverse through remaining edges
for(int j = 0; j < graph.get(i).size(); j++)
if (visited[graph.get(i).get(j)] == 0)
{
b |= print_euler(graph.get(i).get(j),
visited, count);
}
// If the euler path is found
if (b)
{
path.add(arr.get(i));
return true;
}
// Else unmark the node
else
{
visited[i] = 0;
count--;
return false;
}
}
// Function to create the graph and
// print the required path
static void connect()
{
int n = arr.size();
graph = new ArrayList<List<Integer>>(n);
for(int i = 0; i < n; i++)
{
graph.add(new ArrayList<Integer>());
}
// Connect the nodes
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
if (i == j)
continue;
// If the last character matches with the
// first character
if (arr.get(i).charAt((arr.get(i).length()) - 1) ==
arr.get(j).charAt(0))
{
graph.get(i).add(j);
}
}
}
// Print the path
for(int i = 0; i < n; i++)
{
int []visited = new int[n];
int count = 0;
// If the euler path starts
// from the ith node
if (print_euler(i, visited, count))
break;
}
// Print the euler path
for(int i = path.size() - 1; i >= 0; i--)
{
System.out.print(path.get(i));
if (i != 0)
System.out.print(" ");
}
}
// Driver code
public static void main(String []args)
{
arr.add("451");
arr.add("378");
arr.add("123");
arr.add("1254");
// Create graph and print the path
connect();
}
}
// This code is contributed by pratham76
Python3
# Python3 implementation of the approach
# Print eulerian path
def print_euler(i, visited, count):
# Mark node as visited
# and increase the count
visited[i] = 1
count += 1
# If all the nodes are visited then
# we have traversed the euler path
if count == len(graph):
path.append(arr[i])
return True
# Check if the node lies in euler path
b = False
# Traverse through remaining edges
for j in range(0, len(graph[i])):
if visited[graph[i][j]] == 0:
b |= print_euler(graph[i][j], visited, count)
# If the euler path is found
if b:
path.append(arr[i])
return True
# Else unmark the node
else:
visited[i] = 0
count -= 1
return False
# Function to create the graph
# and print the required path
def connect():
n = len(arr)
# Connect the nodes
for i in range(0, n):
for j in range(0, n):
if i == j:
continue
# If the last character matches
# with the first character
if arr[i][-1] == arr[j][0]:
graph[i].append(j)
# Print the path
for i in range(0, n):
visited = [0] * n
count = 0
# If the euler path starts
# from the ith node
if print_euler(i, visited, count):
break
# Print the euler path
for i in range(len(path) - 1, -1, -1):
print(path[i], end="")
if i != 0:
print(" ", end="")
# Driver code
if __name__ == "__main__":
# To store the array elements
arr = []
arr.append("451")
arr.append("378")
arr.append("123")
arr.append("1254")
# Adjacency list for the graph nodes
graph = [[] for i in range(len(arr))]
# To store the euler path
path = []
# Create graph and print the path
connect()
# This code is contributed by Rituraj Jain
C#
// C# implementation of the approach
using System;
using System.Collections;
using System.Collections.Generic;
class GFG
{
// To store the array elements
static List<string> arr = new List<string>();
// Adjacency list for the graph nodes
static List<List<int> > graph= new List<List<int>>();
// To store the euler path
static List<string> path = new List<string>();
// Print eulerian path
static bool print_euler(int i, int []visited, int count)
{
// Mark node as visited
// and increase the count
visited[i] = 1;
count++;
// If all the nodes are visited
// then we have traversed the euler path
if (count == graph.Count) {
path.Add(arr[i]);
return true;
}
// Check if the node lies in euler path
bool b = false;
// Traverse through remaining edges
for (int j = 0; j < graph[i].Count; j++)
if (visited[graph[i][j]] == 0) {
b |= print_euler(graph[i][j], visited, count);
}
// If the euler path is found
if (b) {
path.Add(arr[i]);
return true;
}
// Else unmark the node
else {
visited[i] = 0;
count--;
return false;
}
}
// Function to create the graph and
// print the required path
static void connect()
{
int n = arr.Count;
graph=new List<List<int>>(n);
for(int i = 0; i < n; i++)
{
graph.Add(new List<int>());
}
// Connect the nodes
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j)
continue;
// If the last character matches with the
// first character
if (arr[i][(arr[i].Length) - 1] == arr[j][0]) {
graph[i].Add(j);
}
}
}
// Print the path
for (int i = 0; i < n; i++) {
int []visited = new int[n];
int count = 0;
// If the euler path starts
// from the ith node
if (print_euler(i, visited, count))
break;
}
// Print the euler path
for (int i = path.Count - 1; i >= 0; i--) {
Console.Write(path[i]);
if (i != 0)
Console.Write(" ");
}
}
// Driver code
public static void Main(params string []args)
{
arr.Add("451");
arr.Add("378");
arr.Add("123");
arr.Add("1254");
// Create graph and print the path
connect();
}
}
// This code is contributed by rutvik_56.
Producción:
1254 451 123 378
Complejidad de tiempo: O(N* log(N))
Espacio Auxiliar : O(N)
Publicación traducida automáticamente
Artículo escrito por andrew1234 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA