Liste di adiacenza dall’input
Costruire il grafo fornito dalle gare
Liste di adiacenza dall’input è una lezione Competitive Programming Academy gratuita su CoddyKit. Questa è la lezione 1 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Competitive Programming Academy, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Competitive Programming Academy include 4 lezioni in totale.
Che cos’è davvero un grafo
Un grafo è semplicemente un insieme di punti, chiamati nodi, collegati da linee, chiamate archi. Le città collegate da strade formano un grafo che già conosce. 🗺️
Nodi e archi
Ogni nodo rappresenta un’entità e ogni arco indica che due nodi sono collegati. Nei grafi delle competizioni, i nodi sono generalmente numerati da 1 a n.
La lista di adiacenza
La struttura di dati preferita nelle competizioni è la lista di adiacenza: per ogni nodo si conserva l’elenco dei suoi vicini diretti.
adj = [[] for _ in range(n + 1)]Perché non usare una matrice
Una matrice richiede memoria pari a n al quadrato, che cresce rapidamente per valori grandi di n. Una lista di adiacenza memorizza solo gli archi esistenti, quindi scala meglio.
Leggere la prima riga
La maggior parte degli input inizia con due numeri: n nodi e m archi. Si leggono per primi per sapere quanti archi aspettarsi.
n, m = map(int, input().split())Un arco per riga
Ognuna delle m righe successive fornisce una coppia u v. Quel singolo arco indica che u e v sono collegati direttamente.
u, v = map(int, input().split())Non orientato significa in entrambe le direzioni
Per un arco non orientato, si aggiunge il collegamento in entrambe le direzioni. È possibile passare da u a v e da v a u.
adj[u].append(v)
adj[v].append(u)Orientato significa in una sola direzione
Per un arco orientato, si memorizza solo il collegamento da u a v. È importante leggere attentamente il testo del problema per sapere quale tipo di grafo si sta usando.
adj[u].append(v)Costruirla con un ciclo
Si esegue un ciclo m volte, si legge ogni coppia e si riempiono le liste. Al termine del ciclo, la lista di adiacenza contiene l’intero grafo.
for _ in range(m):
u, v = map(int, input().split())
adj[u].append(v)
adj[v].append(u)Indicizzazione da 1 e da 0
Se i nodi iniziano da 1, la lista va dimensionata come n più 1, così l’indice n è valido. Confondere l’indicizzazione causa errori difficili da individuare.
Visitare i vicini di un nodo
Una volta costruito il grafo, esplorarlo è semplice: si scorre adj di un nodo per raggiungere ogni vicino in un solo passaggio.
for nb in adj[u]:
print(nb)Verifica rapida
È stato letto un arco non orientato u v. Che cosa si deve memorizzare?
Riepilogo
Ora è possibile costruire un grafo come lista di adiacenza: si leggono n e m, si percorrono gli archi e si aggiungono entrambe le direzioni quando il grafo è non orientato. 🎉
Domande Frequenti
La lezione «Liste di adiacenza dall’input» è gratuita?
Sì — il testo completo di «Liste di adiacenza dall’input» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Competitive Programming Academy, passa a CoddyKit PRO. Il corso Competitive Programming Academy include 4 lezioni in totale.
Cosa imparerò in «Liste di adiacenza dall’input»?
Costruire il grafo fornito dalle gare Eserciti Competitive Programming Academy con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Competitive Programming Academy?
Non è richiesta alcuna esperienza precedente. Competitive Programming Academy su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 1 di 4.
Quanto tempo richiede la lezione «Liste di adiacenza dall’input»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Competitive Programming Academy?
Sì. Ogni lezione Competitive Programming Academy include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Liste di adiacenza dall’input
- BFS per i cammini minimi non pesati
- DFS, ricorsione e stack iterativi
- Componenti connesse e flood fill