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

🇨🇱 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.

ProblemaCompetenciaDificultad
Viaje a la playa2022 Nacional🟢 fácil
Ajedrez2015 Nacional🟡 media
Risk2016 Nacional🟡 media
Naruto vs Sasuke pelea completa (español latino)2017 Clasificatoria🟡 media
Ociman y su pogo stick2018 Nacional🟡 media
Por una ciudad más caminable2021 Nacional🟡 media
La cueva de hielo2016 Clasificatoria🟡 media
Guerrera Dragona2024 Nacional🟡 media
La doctora Jones y el templo de las mil almas perdidas2019 Nacional🔴 difícil
Figuras2023 Nacional🔴 difícil
Ca-chi-pún2017 Clasificatoria🔴 difícil
Transbordo en el aeropuerto2017 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.

ProblemaAñoMedia (puntos parciales)Lograron 100
Connecting Supertrees202078/10044%
World Map202548/1004%
Obstacles for a Llama202545/1003%
Sphinx’s Riddle202435/1002%
Longest Trip202334/1003%
Magic City202634/1001%
Keys202131/1005%
Werewolf201831/1005%
Fountain Parks202130/1003%
Thousands Islands202229/1002%
Split the Attractions201927/1002%
Ancient Books201726/1005%
Robot Contest202326/1000%
Roller Coaster Railroad201626/1001%
Simurgh201718/1001%
Highway Tolls201816/100<1%
Sky Walking201913/100<1%
Toy Train201710/1001%