DSU polkujen pakkauksella
Etsi ja yhdistä lähes vakioajassa
DSU polkujen pakkauksella on ilmainen Competitive Programming Academy-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 Competitive Programming Academy-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. Competitive Programming Academy-kurssilla on yhteensä 4 oppituntia.
Mitä DSU seuraa
Disjoint Set Union pitää alkiot ryhmiteltyinä toistensa kanssa leikkaamattomiin joukkoihin, joten voitte tarkistaa, kuuluvatko kaksi asiaa jo samaan joukkoon. 🤝
Joukot puina
DSU tallentaa jokaisen joukon puuna. Jokainen alkio osoittaa parent-alkioon, ja ylimmän tason solmu eli juuri on koko ryhmän yksikäsitteinen nimi.
Parent-taulukko
Säilytätte kaikki nämä linkit yhdessä taulukossa. Alustakaa jokainen alkio omaksi parent-alkiokseen, mikä tarkoittaa, että jokainen aloittaa omassa joukossaan.
parent = list(range(n))Juuren etsiminen
find-operaatio kulkee parent-linkkejä ylöspäin, kunnes alkio osoittaa itseensä. Tämä itseensä osoittava solmu on joukon tunnistava juuri.
while parent[x] != x:
x = parent[x]Pitkät ketjut haittaavat
Ilman huolellista toteutusta joukoista voi muodostua pitkiä ja kapeita ketjuja. Silloin find etenee solmu kerrallaan, ja yksi kysely voi maksaa O(n), mikä on aivan liian hidasta.
Path compression käyttöön
Path compression ratkaisee tämän: juurta etsiessänne ohjaatte jokaisen vieraillun solmun suoraan juureen, jolloin puu litistyy seuraavaa käyttökertaa varten. ⚡
Rekursiivinen pakkaus
Siistein tapa on käyttää rekursiota. Etsikää juuri ja tallentakaa se sitten takaisin kohtaan parent[x] ennen paluuta, jolloin linkki lyhenee pysyvästi.
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]Kaksi alkiota, sama joukko?
Voitte tarkistaa alkioiden yhteyden vertaamalla niiden juuria. Jos find(a) equals find(b), ne kuuluvat samaan ryhmään; muuten ne ovat edelleen erillään.
if find(a) == find(b):
print("connected")Kahden joukon yhdistäminen
union-operaatio yhdistää ryhmät ohjaamalla toisen juuren toiseen. Yksi rivi yhdistää kaksi kokonaista puuta yhdeksi joukoksi.
def union(a, b):
parent[find(a)] = find(b)Miksi se on niin nopea
Pelkkää pakkausta käyttämällä operaatiot toimivat keskimäärin suunnilleen ajassa O(log n), ja rank-menetelmään yhdistettynä yhden kyselyn aika on lähes vakio.
Missä DSU loistaa
DSU ratkaisee yhteyksien selvittämiseen liittyviä ongelmia: ystäväpiirit, verkon komponentit ja Kruskalin virittävä puu perustuvat kaikki nopeisiin find- ja union-operaatioihin. 🌐
Pikatarkistus
Miettikää, mitä path compression todella muuttaa.
Kertaus
Rakensitte DSU:n: parent-taulukon, find-operaation juuren hakemiseen ja union-operaation yhdistämiseen. Path compression pitää sen salamannopeana. Hienoa työtä! 🎉
Opi Python 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
- 30
- Oppitunnit
- 120
Usein kysytyt kysymykset
Onko oppitunti ”DSU polkujen pakkauksella” ilmainen?
Kyllä – oppitunnin ”DSU polkujen pakkauksella” 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 Competitive Programming Academy-kurssin, päivitä CoddyKit PROhon. Competitive Programming Academy-kurssilla on yhteensä 4 oppituntia.
Mitä opin oppitunnilla ”DSU polkujen pakkauksella”?
Etsi ja yhdistä lähes vakioajassa Harjoittelet Competitive Programming Academy-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.
Tarvitsenko kokemusta aloittaakseni Competitive Programming Academy-opiskelun?
Aiempi kokemus ei ole tarpeen. CoddyKitin Competitive Programming Academy-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 1/4.
Kuinka kauan ”DSU polkujen pakkauksella”-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ä Competitive Programming Academy-oppitunnilla?
Kyllä. Jokainen Competitive Programming Academy-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
- DSU polkujen pakkauksella
- Yhdistäminen rankin ja komponenttien perusteella
- Kruskalin pienin virittävä puu
- Primin MST keon avulla