BFS-DFS
Solución
Explicación
Para satisfacer el orden BFS, podemos conectar el nodo 1 con todos los demás nodos, colocándolos todos en el mismo nivel. Esto garantiza el recorrido BFS correcto.
Para satisfacer el orden DFS, podemos formar un camino simple que parte del nodo 1 conectando cada nodo con el siguiente de la lista DFS. Esto asegura un recorrido DFS válido.
Construimos la lista de aristas así:
- Añadiendo aristas del nodo 1 a todos los demás nodos de la lista BFS.
- Añadiendo aristas entre cada par consecutivo de la lista DFS.
Si ambos recorridos listan un segundo nodo distinto, no hay grafo válido, pues el primer hijo del nodo 1 debe ser el mismo en ambos recorridos.
Implementación
Complejidad temporal:
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> bfs(n);
vector<int> dfs(n);
for (int i = 0; i < n; i++) { cin >> bfs[i]; }
for (int i = 0; i < n; i++) { cin >> dfs[i]; }
if (n == 1) {
cout << 0 << endl;
return 0;
}
// first child of node 1 must match
if (bfs[1] != dfs[1]) {
cout << -1 << endl;
return 0;
}
cout << 2 * n - 3 << endl;
for (int i = 1; i < n; i++) { cout << 1 << " " << bfs[i] << endl; }
// skip the edge between node 1 and first child because BFS already covered it
for (int i = 1; i < n - 1; i++) { cout << dfs[i] << " " << dfs[i + 1] << endl; }
}import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] bfs = new int[n];
int[] dfs = new int[n];
String[] bfsLine = br.readLine().split(" ");
String[] dfsLine = br.readLine().split(" ");
for (int i = 0; i < n; i++) { bfs[i] = Integer.parseInt(bfsLine[i]); }
for (int i = 0; i < n; i++) { dfs[i] = Integer.parseInt(dfsLine[i]); }
if (n == 1) {
System.out.println(0);
return;
}
// first child of node 1 must match
if (bfs[1] != dfs[1]) {
System.out.println(-1);
return;
}
System.out.println(2 * n - 3);
for (int i = 1; i < n; i++) { System.out.println("1 " + bfs[i]); }
// skip the edge between node 1 and first child because BFS already covered it
for (int i = 1; i < n - 1; i++) {
System.out.println(dfs[i] + " " + dfs[i + 1]);
}
}
}n = int(input())
bfs = list(map(int, input().split()))
dfs = list(map(int, input().split()))
if n == 1:
print(0)
exit()
# first child of node 1 must match
if bfs[1] != dfs[1]:
print(-1)
exit()
print(2 * n - 3)
for i in range(1, n):
print(1, bfs[i])
# skip the edge between node 1 and first child because BFS already covered it
for i in range(1, n - 1):
print(dfs[i], dfs[i + 1])Solución en video
Por David Zhou