DSU mit Pfadkompression
Finden und vereinigen Sie Mengen in nahezu konstanter Zeit
DSU mit Pfadkompression ist eine kostenlose Competitive Programming Academy-Lektion auf CoddyKit. Dies ist Lektion 1 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Competitive Programming Academy-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
Was ein DSU verfolgt
Eine Disjoint Set Union hält Elemente in nicht überlappenden Mengen gruppiert, sodass Sie prüfen können, ob zwei Dinge bereits zusammengehören. 🤝
Mengen als Bäume
DSU speichert jede Menge als Baum. Jedes Element verweist auf ein Elternelement, und der oberste Knoten, die Wurzel, ist der eindeutige Name der gesamten Gruppe.
Das Eltern-Array
Sie speichern all diese Verknüpfungen in einem Array. Zunächst ist jedes Element sein eigener Vorgänger; jedes Element beginnt also in einer eigenen Menge.
parent = list(range(n))Die Wurzel finden
Die Operation find folgt den Elternverweisen nach oben, bis ein Element auf sich selbst zeigt. Dieser auf sich selbst verweisende Knoten ist die Wurzel, die die Menge identifiziert.
while parent[x] != x:
x = parent[x]Lange Ketten sind problematisch
Ohne geeignete Maßnahmen können Mengen lange, schmale Ketten bilden. Dann arbeitet sich find Knoten für Knoten vor, und eine einzelne Abfrage kann O(n) kosten – viel zu langsam.
Pfadkompression kommt ins Spiel
Pfadkompression behebt dieses Problem: Beim Suchen der Wurzel verweisen Sie jeden besuchten Knoten direkt auf die Wurzel und flachen den Baum für das nächste Mal ab. ⚡
Rekursive Kompression
Am saubersten lässt sich das rekursiv umsetzen. Suchen Sie die Wurzel und speichern Sie sie anschließend vor der Rückgabe in parent[x]
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]Zwei Elemente, dieselbe Menge?
Um zu prüfen, ob zwei Elemente verbunden sind, vergleichen Sie ihre Wurzeln. Wenn find(a) equals find(b) gilt, gehören sie zur selben Gruppe; andernfalls sind sie weiterhin getrennt.
if find(a) == find(b):
print("connected")Zwei Mengen zusammenführen
Die Operation union verbindet Gruppen, indem sie eine Wurzel unter die andere hängt. Eine Zeile verknüpft zwei vollständige Bäume zu einer einzigen Menge.
def union(a, b):
parent[find(a)] = find(b)Warum es so schnell ist
Mit alleiniger Kompression laufen die Operationen amortisiert ungefähr in O(log n). In Kombination mit Rangheuristik erreichen sie nahezu konstante Zeit pro Abfrage.
Wo DSU glänzt
DSU ist besonders nützlich bei Fragen zur Zusammenhängigkeit: Freundeskreise, Netzwerkkomponenten und Kruskals Spannbaum beruhen alle auf schnellem find und union. 🌐
Schnelltest
Überlegen Sie, was die Pfadkompression tatsächlich verändert.
Zusammenfassung
Sie haben einen DSU aufgebaut: ein Eltern-Array, find zum Ermitteln der Wurzel und union zum Zusammenführen. Die Pfadkompression hält ihn blitzschnell. Gute Arbeit! 🎉
Häufig gestellte Fragen
Ist die Lektion „DSU mit Pfadkompression“ kostenlos?
Ja — der vollständige Text von „DSU mit Pfadkompression“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Competitive Programming Academy-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „DSU mit Pfadkompression“?
Finden und vereinigen Sie Mengen in nahezu konstanter Zeit Du übst Competitive Programming Academy mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um Competitive Programming Academy zu starten?
Keine Vorkenntnisse erforderlich. Competitive Programming Academy auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 1 von 4.
Wie lange dauert die Lektion „DSU mit Pfadkompression“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser Competitive Programming Academy-Lektion Code schreiben und ausführen?
Ja. Jede Competitive Programming Academy-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- DSU mit Pfadkompression
- Vereinigung nach Rang und Komponenten
- Minimaler Spannbaum mit Kruskal
- Prims MST mit einem Heap