El último y el más exigente, para cuando los anteriores ya salen solos. Quince páginas de un sitio y veintitrés enlaces: demasiado para seguir la traza de memoria, que es el tamaño en que estos algoritmos dejan de ser un ejercicio de papel. Dos páginas están en el mismo bloque cuando se puede ir y volver entre ellas siguiendo enlaces.
Veintitrés enlaces: 0 → 1, 1 → 2, 2 → 3, 3 → 0, 4 → 5, 5 → 4, 6 → 7, 7 → 8, 8 → 6, 10 → 11, 11 → 10, 13 → 14, 14 → 13, 1 → 4, 2 → 6, 5 → 6, 5 → 9, 7 → 9, 8 → 10, 9 → 12, 11 → 12, 12 → 13, 10 → 14.
¿Cuántos bloques de páginas mutuamente alcanzables hay?
La lista es ord, ya calculada por la
primera búsqueda en profundidad y leída de izquierda a derecha. Cada
llamada que encuentra su página sin asignar pinta un bloque entero; las
demás se devuelven sin hacer nada y quedan tachadas.
| Bloque | Arranca en | Páginas | Tamaño |
|---|
¿Cuántas aristas tiene el grafo de componentes?
Borre las puntas de los enlaces y quedan veinte aristas sin dirección. Dos preguntas sobre ese grafo.
Componentes conexos y puntos de articulación del sitio sin direcciones:
El administrador agrega un enlace de vuelta desde la página 14 hasta la portada, 14 → 0.
¿Cuántos bloques quedan entonces?
Sin solución aquí. Tres preguntas sobre el mismo sitio.