Grafos
BFS/DFS, caminos mínimos, componentes, flujo.
Volver a los 11 temas · Referencia · temarios: Syllabus OCI · Syllabus IOI.
📍 Clases relacionadas: módulos 15 · 16 · 18 de la Ruta de Aprendizaje.
📋 En el temario OCI: solo en la fase Nacional (⊗): representación, BFS/DFS, distancias con BFS y con Dijkstra.
Un grafo es cualquier cosa hecha de elementos y conexiones: ciudades unidas por rutas, personas que se conocen, casillas de un tablero por donde se puede caminar. Casi todo enunciado que hable de llegar, conectar o alcanzar es un grafo disfrazado.
📌 Qué abarca
- Representación: lista y matriz de adyacencia.
- Recorridos: BFS, DFS, componentes conexas, clausura transitiva.
- Orden topológico y DAG; caminos/ciclos de Euler.
- Caminos mínimos: BFS (no ponderado), Dijkstra O(M log N), Bellman-Ford (pesos negativos, detección de ciclos), Floyd-Warshall O(N³).
- MST: Kruskal (con DSU) y Prim.
- Biconexión: puentes y puntos de articulación (Tarjan).
- SCC (conexión fuerte): Tarjan / Kosaraju.
- Bipartito (2-coloreo) y matching bipartito por caminos aumentantes (Kuhn) O(V·E).
- Flujo máximo / corte mínimo por Ford-Fulkerson / Edmonds-Karp (caminos aumentantes) y la dualidad max-flow = min-cut.
⛔ Fuera del syllabus IOI
- Dinic, push-relabel y otros flujos “eficientes”; min-cost flow.
- Matching general (no bipartito / Blossom).
- LexBFS, max-adjacency search, matroides, treewidth.
- Test de planaridad (los grafos planares como concepto sí entran).
- Separadores de grafos planares — ojo, no confundir con la centroid decomposition de Árboles, que el syllabus sí incluye.
Los problemas de flujo/matching se diseñan para que esa eficiencia extra no dé ventaja.
🎯 En competencia
En la OCI — No aparece en la Regional. En la Nacional es el tema nuevo: grafos implícitos en tableros (laberintos, casillas alcanzables), BFS para distancias sin peso y Dijkstra con peso. Si vas a la nacional, dominar el BFS sobre una grilla vale más que cualquier algoritmo avanzado. En este vault hay 12 problemas OCI del tema (9 de fases nacionales y 3 de clasificatorias IOI); están en la tabla de abajo.
En la IOI — Modelar el problema como grafo suele ser el 80% del trabajo. Muchas subtareas se aseguran con un BFS/DFS o un Dijkstra directo antes de la solución completa.
⚠️ La trampa típica
Dos que aparecen todo el tiempo: las distancias de Dijkstra se desbordan si usas int (10⁵ aristas × 10⁹ no cabe), y un DFS recursivo sobre 10⁶ nodos puede reventar la pila (RTE). Ver Complejidad computacional.
⚙️ Algoritmos y técnicas
- BFS
- Bellman-Ford
- DFS
- Dijkstra
- Flood fill
- Floyd-Warshall
- Flujo máximo (Ford-Fulkerson)
- Kruskal (MST)
- Matching bipartito (Kuhn)
- Orden topológico (Kahn)
- Prim (MST)
- Puentes y puntos de articulación
- SCC (Tarjan)
🇨🇱 Problemas OCI (en español)
Empieza por acá: son problemas oficiales chilenos, con enunciado en español y mirror para enviar. Consulta la orientación de estudio al comienzo de esta página. La dificultad orienta la elección, pero no garantiza una solución completa.
| Problema | Competencia | Dificultad |
|---|---|---|
| Viaje a la playa | 2022 Nacional | 🟢 fácil |
| Ajedrez | 2015 Nacional | 🟡 media |
| Risk | 2016 Nacional | 🟡 media |
| Naruto vs Sasuke pelea completa (español latino) | 2017 Clasificatoria | 🟡 media |
| Ociman y su pogo stick | 2018 Nacional | 🟡 media |
| Por una ciudad más caminable | 2021 Nacional | 🟡 media |
| La cueva de hielo | 2016 Clasificatoria | 🟡 media |
| Guerrera Dragona | 2024 Nacional | 🟡 media |
| La doctora Jones y el templo de las mil almas perdidas | 2019 Nacional | 🔴 difícil |
| Figuras | 2023 Nacional | 🔴 difícil |
| Ca-chi-pún | 2017 Clasificatoria | 🔴 difícil |
| Transbordo en el aeropuerto | 2017 Nacional | 🔴 difícil |
🌍 Problemas IOI
De más abordable a más duro, según el puntaje promedio que sacaron los competidores: una media alta sugiere más puntos parciales accesibles, no más soluciones completas. Consulta también el porcentaje de 100 y los prerrequisitos.
| Problema | Año | Media (puntos parciales) | Lograron 100 |
|---|---|---|---|
| Connecting Supertrees | 2020 | 78/100 | 44% |
| World Map | 2025 | 48/100 | 4% |
| Obstacles for a Llama | 2025 | 45/100 | 3% |
| Sphinx’s Riddle | 2024 | 35/100 | 2% |
| Longest Trip | 2023 | 34/100 | 3% |
| Magic City | 2026 | 34/100 | 1% |
| Keys | 2021 | 31/100 | 5% |
| Werewolf | 2018 | 31/100 | 5% |
| Fountain Parks | 2021 | 30/100 | 3% |
| Thousands Islands | 2022 | 29/100 | 2% |
| Split the Attractions | 2019 | 27/100 | 2% |
| Ancient Books | 2017 | 26/100 | 5% |
| Robot Contest | 2023 | 26/100 | 0% |
| Roller Coaster Railroad | 2016 | 26/100 | 1% |
| Simurgh | 2017 | 18/100 | 1% |
| Highway Tolls | 2018 | 16/100 | <1% |
| Sky Walking | 2019 | 13/100 | <1% |
| Toy Train | 2017 | 10/100 | 1% |