Naboskapslister fra inndata
Bygg grafen som konkurranseoppgaver gir deg
Naboskapslister fra inndata er en gratis leksjon i Competitive Programming Academy på CoddyKit. Dette er leksjon 1 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Competitive Programming Academy, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Competitive Programming Academy inneholder totalt 4 leksjoner.
Hva en graf egentlig er
En graf består ganske enkelt av punkter kalt noder, som er forbundet med linjer kalt kanter. Et veinett mellom byer er en graf De allerede kjenner. 🗺️
Noder og kanter
Hver node representerer en ting, og hver kant sier at to noder er forbundet. I konkurranseoppgaver nummereres noder vanligvis fra 1 til n.
Nabolisten
Standardlagringen i konkurranseoppgaver er en naboliste: for hver node lagres en liste over de direkte naboene.
adj = [[] for _ in range(n + 1)]Hvorfor ikke en matrise
En matrise bruker n² minne, noe som blir uhåndterlig for store n. En naboliste lagrer bare kanter som faktisk finnes, og skalerer derfor bedre.
Les den første linjen
De fleste inndata begynner med to tall: n noder og m kanter. Les dem først, slik at De vet hvor mange kanter som skal leses.
n, m = map(int, input().split())Én kant per linje
Hver av de neste m linjene inneholder et par u v. Denne ene kanten betyr at u og v er direkte forbundet.
u, v = map(int, input().split())Urettet betyr begge veier
For en urettet kant legges forbindelsen inn i begge retninger. De kan gå fra u til v og fra v til u.
adj[u].append(v)
adj[v].append(u)Rettet betyr én vei
For en rettet kant lagres bare forbindelsen fra u til v. Les oppgaveteksten nøye for å vite hvilken type De har.
adj[u].append(v)Bygg den i en løkke
Gjenta m ganger, les hvert par og fyll listene. Etter løkken inneholder nabolisten hele grafen.
for _ in range(m):
u, v = map(int, input().split())
adj[u].append(v)
adj[v].append(u)1-basert vs. 0-basert indeksering
Hvis noder starter på 1, dimensjoneres listen til n + 1, slik at indeks n er gyldig. Forveksling av indekseringen fører til feil som kan være vanskelige å oppdage.
Besøk naboene til en node
Når grafen er bygget, er utforskingen enkel: gå gjennom adj for en node for å nå hver nabo i ett trinn.
for nb in adj[u]:
print(nb)Hurtigsjekk
De leser en urettet kant u v. Hva skal lagres?
Oppsummering
De kan nå bygge en graf som en naboliste: les n og m, gå gjennom kantene, og legg til begge retninger når grafen er urettet. 🎉
Lær deg Python med en AI-veileder – gratis
Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.
- Kurs
- 30
- Leksjoner
- 120
Ofte stilte spørsmål
Er leksjonen «Naboskapslister fra inndata» gratis?
Ja – hele teksten i «Naboskapslister fra inndata» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Competitive Programming Academy-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Competitive Programming Academy inneholder totalt 4 leksjoner.
Hva lærer jeg i «Naboskapslister fra inndata»?
Bygg grafen som konkurranseoppgaver gir deg Du øver på Competitive Programming Academy med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.
Trenger jeg erfaring for å begynne med Competitive Programming Academy?
Ingen tidligere erfaring er nødvendig. Competitive Programming Academy på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 1 av 4.
Hvor lang tid tar leksjonen «Naboskapslister fra inndata»?
De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.
Kan jeg skrive og kjøre kode i denne Competitive Programming Academy-leksjonen?
Ja. Alle Competitive Programming Academy-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.
Alle leksjonene i dette kurset
- Naboskapslister fra inndata
- BFS for korteste uvektede stier
- DFS, rekursjon og iterative stakker
- Sammenhengende komponenter og flomfylling