Skip to Content

BFS-DFS

Análisis oficial (C++) 

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: O(N)\mathcal{O}(N)

#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

Video de YouTube (zJ8cVWbFcds)