Listas de adyacencia a partir de la entrada
Construya el grafo que proporcionan los concursos
Listas de adyacencia a partir de la entrada es una lección gratuita de Competitive Programming Academy en CoddyKit. Esta es la lección 1 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Competitive Programming Academy, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Competitive Programming Academy incluye 4 lecciones en total.
Qué es realmente un grafo
Un grafo no es más que unos puntos llamados nodos unidos por líneas llamadas aristas. Las ciudades conectadas por carreteras forman un grafo que ya conoce. 🗺️
Nodos y aristas
Cada nodo representa algo, y cada arista indica que dos nodos están conectados. En las competiciones, los grafos suelen numerar los nodos del 1 al n.
La lista de adyacencia
La estructura de almacenamiento habitual en las competiciones es una lista de adyacencia: para cada nodo, se conserva una lista de sus vecinos directos.
adj = [[] for _ in range(n + 1)]Por qué no una matriz
Una matriz utiliza n al cuadrado de memoria, lo que se vuelve enorme cuando n es grande. Una lista de adyacencia solo almacena las aristas existentes, por lo que escala mejor.
Leer la primera línea
La mayoría de las entradas comienzan con dos números: n nodos y m aristas. Léalos primero para saber cuántas aristas debe esperar.
n, m = map(int, input().split())Una arista por línea
Cada una de las siguientes m líneas proporciona un par u v. Esa única arista significa que u y v están conectados directamente.
u, v = map(int, input().split())No dirigido significa en ambos sentidos
Para una arista no dirigida, añada la conexión en ambos sentidos. Puede desplazarse de u a v y de v a u.
adj[u].append(v)
adj[v].append(u)Dirigido significa en un solo sentido
Para una arista dirigida, almacene únicamente la conexión de u a v. Lea atentamente el enunciado para saber qué tipo tiene.
adj[u].append(v)Construirlo en un bucle
Repita el bucle m veces, lea cada par y rellene las listas. Después del bucle, su lista de adyacencia contendrá el grafo completo.
for _ in range(m):
u, v = map(int, input().split())
adj[u].append(v)
adj[v].append(u)Indexación desde 1 frente a desde 0
Si los nodos comienzan en 1, dimensione la lista como n más 1 para que el índice n sea válido. Confundir la indexación provoca errores silenciosos.
Visitar los vecinos de un nodo
Una vez construido el grafo, explorarlo es fácil: recorra adj para un nodo y llegará a cada vecino en un paso.
for nb in adj[u]:
print(nb)Comprobación rápida
Ha leído una arista no dirigida u v. ¿Qué debe almacenar?
Resumen
Ahora puede construir un grafo como una lista de adyacencia: lea n y m, recorra las aristas y añada ambos sentidos cuando la arista no sea dirigida. 🎉
Preguntas frecuentes
¿La lección «Listas de adyacencia a partir de la entrada» es gratis?
Sí — el texto completo de «Listas de adyacencia a partir de la entrada» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Competitive Programming Academy, actualiza a CoddyKit PRO. El curso de Competitive Programming Academy incluye 4 lecciones en total.
¿Qué aprenderé en «Listas de adyacencia a partir de la entrada»?
Construya el grafo que proporcionan los concursos Practicas Competitive Programming Academy con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Competitive Programming Academy?
No se requiere experiencia previa. Competitive Programming Academy en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 1 de 4.
¿Cuánto tiempo toma la lección «Listas de adyacencia a partir de la entrada»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Competitive Programming Academy?
Sí. Cada lección de Competitive Programming Academy incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Listas de adyacencia a partir de la entrada
- BFS para caminos mínimos no ponderados
- DFS, recursión y pilas iterativas
- Componentes conexas y flood fill