Vieryslistat syötteestä
Rakenna kilpailutehtävän antama graafi
Vieryslistat syötteestä on ilmainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti CoddyKitissä. Tämä on oppitunti 1/4. Voit lukea koko oppitunnin alta ilmaiseksi ja harjoitella sen jälkeen käytännössä selaimessa sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla. Oppitunti kuuluu Valmistautuminen ohjelmointihaastatteluihin-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.
Mikä graafi todella on
Graafi koostuu solmuiksi kutsutuista pisteistä, jotka on yhdistetty kaariksi kutsutuilla viivoilla. Teiden yhdistämät kaupungit muodostavat graafin, jonka tunnette jo ennestään. 🗺️
Solmut ja kaaret
Jokainen solmu edustaa jotakin kohdetta, ja jokainen kaari kertoo kahden solmun olevan yhteydessä toisiinsa. Kilpailuohjelmoinnin graafeissa solmut numeroidaan yleensä 1:stä n:ään.
Vierekkäisyyslista
Kilpailuohjelmoinnissa tavallisin tallennustapa on vierekkäisyyslista: jokaiselle solmulle tallennetaan luettelo sen suorista naapureista.
adj = [[] for _ in range(n + 1)]Miksi ei matriisia
Matriisi käyttää n:n neliön verran muistia, mikä kasvaa suurilla n:n arvoilla valtavaksi. Vierekkäisyyslista tallentaa vain olemassa olevat kaaret, joten se skaalautuu paremmin.
Ensimmäisen rivin lukeminen
Useimmat syötteet alkavat kahdella luvulla: n solmulla ja m kaarella. Lukekaa ne ensin, jotta tiedätte, kuinka monta kaarta on odotettavissa.
n, m = map(int, input().split())Yksi kaari riviä kohden
Jokainen seuraavista m rivistä antaa parin u v. Tämä yksittäinen kaari tarkoittaa, että u ja v ovat suoraan yhteydessä toisiinsa.
u, v = map(int, input().split())Suuntaamaton tarkoittaa molempia suuntia
Jos kaari on suuntaamaton, lisätkää yhteys molempiin suuntiin. Voitte kulkea solmusta u solmuun v ja solmusta v solmuun u.
adj[u].append(v)
adj[v].append(u)Suunnattu tarkoittaa yhtä suuntaa
Jos kaari on suunnattu, tallentakaa vain yhteys u:sta v:hen. Lukekaa tehtävänanto huolellisesti, jotta tiedätte, kumman tyyppinen graafi on kyseessä.
adj[u].append(v)Rakentaminen silmukassa
Toistakaa silmukkaa m kertaa, lukekaa jokainen pari ja täyttäkää listat. Silmukan jälkeen vierekkäisyyslista sisältää koko graafin.
for _ in range(m):
u, v = map(int, input().split())
adj[u].append(v)
adj[v].append(u)Indeksointi alkaen yhdestä tai nollasta
Jos solmut alkavat numerosta 1, määrittäkää listan kooksi n plus 1, jotta indeksi n on kelvollinen. Indeksoinnin sekoittaminen aiheuttaa huomaamattomia virheitä.
Solmun naapureiden läpikäynti
Kun graafi on rakennettu, sen tutkiminen on helppoa: käykää solmun adj läpi saavuttaaksenne jokaisen naapurin yhdellä askeleella.
for nb in adj[u]:
print(nb)Pikatarkistus
Luette suuntaamattoman kaaren u v. Mitä tallennatte?
Kertaus
Osaatte nyt rakentaa graafin vierekkäisyyslistana: lukekaa n ja m, käykää kaaret silmukassa läpi ja lisätkää yhteys molempiin suuntiin, kun kaari on suuntaamaton. 🎉
Opi Valmistautuminen ohjelmointihaastatteluihin tekoälytuutorin avulla — ilmaiseksi
Kirjoita ja suorita oikeaa koodia selaimessa, saa välitöntä apua tekoälytuutorilta ympäri vuorokauden ja jatka siitä, mihin jäit, verkossa tai sovelluksessa.
- Kurssit
- 90
- Oppitunnit
- 360
Usein kysytyt kysymykset
Onko oppitunti ”Vieryslistat syötteestä” ilmainen?
Kyllä – oppitunnin ”Vieryslistat syötteestä” koko tekstin voi lukea täällä verkossa ilmaiseksi. Jos haluat harjoitella interaktiivisesti sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla sekä avata koko Valmistautuminen ohjelmointihaastatteluihin-kurssin, päivitä CoddyKit PROhon. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.
Mitä opin oppitunnilla ”Vieryslistat syötteestä”?
Rakenna kilpailutehtävän antama graafi Harjoittelet Valmistautuminen ohjelmointihaastatteluihin-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.
Tarvitsenko kokemusta aloittaakseni Valmistautuminen ohjelmointihaastatteluihin-opiskelun?
Aiempi kokemus ei ole tarpeen. CoddyKitin Valmistautuminen ohjelmointihaastatteluihin-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 1/4.
Kuinka kauan ”Vieryslistat syötteestä”-oppitunnin suorittaminen kestää?
Useimmat CoddyKitin oppitunnit kestävät noin 5–10 minuuttia. Jokainen oppitunti on lyhyt ja interaktiivinen, joten edistyt tasaisesti ja voit jatkaa siitä, mihin jäit – sekä verkossa että sovelluksessa.
Voinko kirjoittaa ja suorittaa koodia tällä Valmistautuminen ohjelmointihaastatteluihin-oppitunnilla?
Kyllä. Jokainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti sisältää sisäänrakennetun koodieditorin, joten voit kirjoittaa ja suorittaa oikeaa koodia suoraan selaimessa ja saada välitöntä palautetta tekoälyltä – paikallista asennusta ei tarvita.
Kaikki tämän kurssin oppitunnit
- Vieryslistat syötteestä
- BFS painottamattomien polkujen lyhimmille reiteille
- DFS, rekursio ja iteratiiviset pinot
- Yhtenäiset komponentit ja flood fill