Dada una array 2D arr[][] que consiste en N pares de enteros tales que los dos elementos en cada fila indican que son elementos adyacentes en la array original. La tarea es construir una array con pares dados de elementos adyacentes de arr[] .
Ejemplos
Entrada: arr[] = {{5, 1 }, {3, 4 }, {3, 5}}
Salida: 4 3 5 1
Explicación: La array se puede construir usando las siguientes operaciones:
Operación 1: Los elementos 4 y Tengo un solo vecino. Por lo tanto, pueden ser el primer o el último elemento de la array original. Considerando que 4 es el primer elemento de la array original, A[] = {4}.
Operación 2: Coloque 3 junto a 4. Por lo tanto, A[] = {4, 3}
Operación 3: Coloque 5 junto a 3. Por lo tanto, A[] = {4, 3, 5}.
Operación 4: Coloque 1 como el último elemento de la array. Por lo tanto, A[] = {4, 3, 5, 1}.Entrada: arr[] = {{8, 11}, {-3, 6}, {-3, 8}}
Salida: 6 -3 8 11
Enfoque: el problema se puede resolver utilizando Hashing y DFS . Siga los pasos a continuación para resolver el problema:
- Inicialice una lista de adyacencia usando un Map , digamos mp , para almacenar y asignar elementos vecinos a cada elemento.
- Inicialice un vector , digamos res , para almacenar los elementos originales en la array.
- Comience a crear la array original a partir de los elementos de las esquinas. Por lo tanto, encuentre los elementos que tienen un solo vecino . Puede ser el primero o el último elemento de la array original.
- Inserte el elemento obtenido en res .
- Recorra cada elemento en la lista de adyacencia y verifique si sus vecinos son visitados o no.
- Inserte los vecinos no visitados en el vector res y recorra todos los vecinos de ese elemento. Repita el paso 5 hasta que se visiten todos los elementos.
- Regresar res .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
// Utility function to find original array
void find_original_array(vector<pair<int, int> >& A)
{
// Map to store all neighbors for each element
unordered_map<int, vector<int> > mp;
// Vector to store original elements
vector<int> res;
// Stotrs which array elements are visited
unordered_map<int, bool> visited;
// Adjacency list to store neighbors
// of each array element
for (auto& it : A) {
mp[it.first].push_back(it.second);
mp[it.second].push_back(it.first);
}
auto it = mp.begin();
// Find the first corner element
for (; it != mp.end(); it++) {
if (it->second.size() == 1) {
break;
}
}
// Stores first element of
// the original array
int adjacent = it->first;
// Push it into the original array
res.push_back(it->first);
// Mark as visited
visited[it->first] = true;
// Traversing the neighbors and check
// if the elements are visited or not
while (res.size() != A.size() + 1) {
// Traverse adjacent elements
for (auto& elements : mp[adjacent]) {
// If element is not visited
if (!visited[elements]) {
// Push it into res
res.push_back(elements);
// Mark as visited
visited[elements] = true;
// Update the next adjacent
adjacent = elements;
}
}
}
// Print original array
for (auto it : res) {
cout << it << " ";
}
}
// Driver Code
int main()
{
// Given pairs of adjacent elements
vector<pair<int, int> > A
= { { 5, 1 }, { 3, 4 }, { 3, 5 } };
find_original_array(A);
return 0;
}
Java
// Java program of the above approach
import java.io.*;
import java.util.*;
class Pair {
int first, second;
Pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
class GFG {
// Utility function to find original array
static void find_original_array(List<Pair> A)
{
// Map to store all neighbors for each element
@SuppressWarnings("unchecked")
Map<Integer, List<Integer> > mp = new HashMap();
// Vector to store original elements
List<Integer> res = new ArrayList<Integer>();
// Stotrs which array elements are visited
@SuppressWarnings("unchecked")
Map<Integer, Boolean> visited = new HashMap();
// Adjacency list to store neighbors
// of each array element
for (Pair it : A) {
List<Integer> temp;
temp = (mp.containsKey(it.first))
? mp.get(it.first)
: new ArrayList<Integer>();
temp.add(it.second);
mp.put(it.first, temp);
temp = (mp.containsKey(it.second))
? mp.get(it.second)
: new ArrayList<Integer>();
temp.add(it.first);
mp.put(it.second, temp);
}
int it = 0;
// Find the first corner element
for (Map.Entry<Integer, List<Integer> > entry :
mp.entrySet()) {
if (entry.getValue().size() == 1) {
it = entry.getKey();
}
}
// Stores first element of
// the original array
int adjacent = it;
// Push it into the original array
res.add(it);
// Mark as visited
visited.put(it, true);
// Traversing the neighbors and check
// if the elements are visited or not
while (res.size() != A.size() + 1) {
// Traverse adjacent elements
for (int elements : mp.get(adjacent)) {
// If element is not visited
if (!visited.containsKey(elements)) {
// Push it into res
res.add(elements);
// Mark as visited
visited.put(elements, true);
// Update the next adjacent
adjacent = elements;
}
}
}
// Print original array
for (int val : res) {
System.out.print(val + " ");
}
}
// Driver Code
public static void main(String[] args)
{
@SuppressWarnings("unchecked")
List<Pair> A = new ArrayList();
A.add(new Pair(5, 1));
A.add(new Pair(3, 4));
A.add(new Pair(3, 5));
find_original_array(A);
}
}
// This code is contributed by jithin.
Python3
# Python3 program of the above approach
# Utility function to find original array
def find_original_array(A):
# Map to store all neighbors for each element
mp = [[] for i in range(6)]
# Vector to store original elements
res = []
# Stotrs which array elements are visited
visited = {}
# A djacency list to store neighbors
# of each array element
for it in A:
mp[it[0]].append(it[1])
mp[it[1]].append(it[0])
start = 0
# Find the first corner element
for it in range(6):
if (len(mp[it]) == 1):
start = it + 3
break
# Stores first element of
# the original array
adjacent = start
# Push it into the original array
res.append(start)
# Mark as visited
visited[start] = True
# Traversing the neighbors and check
# if the elements are visited or not
while (len(res) != len(A) + 1):
# Traverse adjacent elements
for elements in mp[adjacent]:
# If element is not visited
if (elements not in visited):
# Push it into res
res.append(elements)
# Mark as visited
visited[elements] = True
# Update the next adjacent
adjacent = elements
# Print original array
print(*res)
# Driver Code
if __name__ == '__main__':
# Given pairs of adjacent elements
A = [[5, 1],[ 3, 4],[ 3, 5]]
find_original_array(A)
# This code is contributed by mohit kumar 29.
C#
// C# program of the above approach
using System;
using System.Collections.Generic;
public class Pair
{
public int first, second;
public Pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
public class GFG
{
// Utility function to find original array
static void find_original_array(List<Pair> A)
{
// Map to store all neighbors for each element
Dictionary<int,List<int>> mp = new Dictionary<int,List<int>>();
// Vector to store original elements
List<int> res = new List<int>();
// Stotrs which array elements are visited
Dictionary<int,bool> visited = new Dictionary<int,bool>();
// Adjacency list to store neighbors
// of each array element
foreach (Pair it in A)
{
List<int> temp;
temp = (mp.ContainsKey(it.first))
? mp[it.first]
: new List<int>();
temp.Add(it.second);
if(!mp.ContainsKey(it.first))
mp.Add(it.first, temp);
else
mp[it.first] = temp;
temp = (mp.ContainsKey(it.second))
? mp[it.second]
: new List<int>();
temp.Add(it.first);
if(!mp.ContainsKey(it.second))
mp.Add(it.second, temp);
else
mp[it.second] = temp;
}
int It = 0;
// Find the first corner element
foreach (int key in mp.Keys)
{
if(mp[key].Count == 1)
{
It=key;
}
}
// Stores first element of
// the original array
int adjacent = It;
// Push it into the original array
res.Add(It);
// Mark as visited
visited.Add(It, true);
// Traversing the neighbors and check
// if the elements are visited or not
while (res.Count != A.Count + 1)
{
// Traverse adjacent elements
foreach (int elements in mp[adjacent])
{
// If element is not visited
if (!visited.ContainsKey(elements))
{
// Push it into res
res.Add(elements);
// Mark as visited
visited.Add(elements, true);
// Update the next adjacent
adjacent = elements;
}
}
}
// Print original array
foreach (int val in res)
{
Console.Write(val + " ");
}
}
// Driver Code
static public void Main (){
List<Pair> A = new List<Pair>();
A.Add(new Pair(5, 1));
A.Add(new Pair(3, 4));
A.Add(new Pair(3, 5));
find_original_array(A);
}
}
// This code is contributed by avanitrachhadiya2155
Javascript
<script>
// JavaScript program of the above approach
// Utility function to find original array
function find_original_array(A){
// Map to store all neighbors for each element
let mp = new Array(6).fill(0).map(()=>[])
// Vector to store original elements
let res = []
// Stotrs which array elements are visited
let visited = new Map();
// A djacency list to store neighbors
// of each array element
for(let it of A){
mp[it[0]].push(it[1])
mp[it[1]].push(it[0])
}
let start = 0
// Find the first corner element
for(let it=0;it<6;it++){
if (mp[it].length == 1){
start = it + 3
break
}
}
// Stores first element of
// the original array
let adjacent = start
// Push it into the original array
res.push(start)
// Mark as visited
visited.set(start , true)
// Traversing the neighbors and check
// if the elements are visited or not
while (res.length != A.length + 1){
// Traverse adjacent elements
for(let elements of mp[adjacent]){
// If element is not visited
if (!visited.has(elements)){
// Push it into res
res.push(elements)
// Mark as visited
visited.set(elements , true)
// Update the next adjacent
adjacent = elements
}
}
}
// Print original array
for(let i of res){
document.write(i," ");
}
}
// Driver Code
// Given pairs of adjacent elements
let A = [[5, 1],[ 3, 4],[ 3, 5]]
find_original_array(A)
// This code is contributed by shinjanpatra
</script>
Producción:
4 3 5 1
Complejidad temporal: O(N 2 )
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por IshwarGupta y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA