Elección voraz
—
—
De la conectividad fuerte a la elección voraz
Tres recorridos guiados: dos BFS, dos DFS de Kosaraju y cambio de monedas.
¿Es fuertemente conexo?
Raíz testigo: A. Avanza para comparar alcanzabilidad en G y Gᵀ.
visitadoContorno neutro: aún no visitado
Kosaraju–Sharir paso a paso
El mismo digrafo se separa en tres componentes fuertes.
{A,B,C}{D,E}{F}
Greedy frente al óptimo
Compara “tomar la moneda mayor” con una solución óptima calculada por programación dinámica.
Óptimo
—
—