Club de Algoritmia: Febrero de Grafos

00_graphs_intro.md

Recursos de las sesiones del mes de Febrero (Grafos)

Todo el mes de febrero estaremos tratando sobre grafos, a continuación los recursos de cada una de las sesiones

• Ene 26 - Introducción a Grafos y Representación
• Feb 02 - BFS (Breadth First Search)
• Feb 09 - Flood-fill y DFS (Depth First Search)
• Feb 16 - Ordenamiento Topológico
• Feb 23 - Kosaraju

Las grabaciones quedan https://www.youtube.com/playlist?list=PLRMfC7A6yJWqJ6x-Xw4Fmrpx-4N5wPjQH

Dudas

Esta abierto el discord para hacer preguntas, ayudarnos, compartir soluciones, etc https://discord.gg/XqQU7DU

01_intro.md

Introducción a grafos

La grabación de esta sesión quedó en https://youtu.be/YTIQ8rSNIwo

• https://ideone.com/Im3AhD Matriz de Adyacencia
• https://ideone.com/cmMdVA Lista de Adyacencia

Para calentar: Papel, lapiz y su lenguaje de programación de preferencia:

• Dibuje un grafo dirigido y otro no dirigido (lo que quiera, estaciones de metro, su arbol genealogico, aeropuertos, etc)
• Represente ambos como lista de adyacencia y como matriz de adyacencia
• Verifique el resultado y preguntese si existen conexión directa de X a Y nodo También puede probar representandolos en un mapa/diccionario/json en lugar de arreglos/matrices.

Problemas de práctica:

• Monk in the real estate https://www.hackerearth.com/practice/algorithms/graphs/graph-representation/practice-problems/algorithm/monk-in-the-real-estate/
• Find the Town Judge https://leetcode.com/problems/find-the-town-judge/

02_bfs.md

BFS (Breadth First Search)

Grabación de la sesión: https://youtu.be/MFHaH0XdXdE

Problemas de práctica:

• Social Network https://www.hackerearth.com/practice/algorithms/graphs/breadth-first-search/practice-problems/algorithm/social-networking-graph/
• Employee Importance https://leetcode.com/problems/employee-importance/
• Flight Plan https://www.hackerearth.com/practice/algorithms/graphs/breadth-first-search/practice-problems/algorithm/traffic-light-2-ee27ba45/
• Rook, Bishop and King https://codeforces.com/problemset/problem/370/A
• Shortest Reach https://www.hackerrank.com/challenges/ctci-bfs-shortest-reach/problem (este fue el que explicó Jose durante la sesión, se recomienda que lo resuelvan por su cuenta)

03_dfs.md

Flood-fill y DFS (Depth First Search)

La grabación de esta sesión quedó en https://www.youtube.com/watch?v=kH-G7dE1bRU

• https://ideone.com/UaPCaH DFS (forma recursiva)
• https://ideone.com/4wQQOY DFS (forma iterativa)
• https://storage.googleapis.com/flood-paint/index.html (Canvas de la caneca de paint)

Problemas para practicar:

• Flood Fill https://leetcode.com/problems/flood-fill/
• Number of Islands https://leetcode.com/problems/number-of-islands/
• Longest path in a tree https://www.spoj.com/problems/PT07Z/

04_toposort.md

Ordenamiento Topológico (Topological Sort)

La grabación quedó en https://www.youtube.com/watch?v=1aNZJ5ORjTI

Implementación de Jorman durante la sesión https://github.com/tille/algorithm-challenges/blob/master/tutorial/toposort/dfs.cpp

Problemas para practicar:

• https://leetcode.com/problems/course-schedule/
• https://practice.geeksforgeeks.org/problems/topological-sort/1
• https://www.spoj.com/problems/RPLA/
• https://www.spoj.com/problems/TOPOSORT/
• https://codeforces.com/contest/510/problem/C

05_kosaraju.md

Kosaraju

La grabación quedó en https://www.youtube.com/watch?v=mCUUk2bVDYQ

La implementación de Esteban durante la sesión https://pastebin.com/RMNLy03D

Problemas para practicar:

Contest de práctica: https://vjudge.net/contest/424356

La ñapa que pidieron:

• https://leetcode.com/problems/number-of-provinces/
• https://leetcode.com/problems/critical-connections-in-a-network/