2025_08.md

Tag 08 - Minimum Spanning Tree mit Union-Find

Aufgabe

Verbindung von Junction Boxes (Dosen) zu Netzwerken basierend auf Distanz:

• Teil 1: Nach 1000 Verbindungen: Größe der 3 größten Netzwerke multiplizieren
• Teil 2: X-Koordinaten des letzten Paares multiplizieren, das alle Dosen zu einem Netzwerk verbindet

Lösung

Eingabeformat

Jede Zeile enthält Koordinaten einer Dose (kommasepariert):

1,2,3
4,5,6
7,8,9

Koordinaten können nur exakt 3 Dimensionen haben (3D).

Algorithmus

Kruskal's MST-Algorithmus mit Union-Find:

1. Datenstrukturen

Union-Find (Disjoint Set Union):

def finde(eltern, i):
    if eltern[i] != i:
        eltern[i] = finde(eltern, eltern[i])
    return eltern[i]

Path Compression:

• Rekursives Finden der Wurzel
• Optimierung: Flacht den Baum ab
• Jeder besuchte Knoten zeigt direkt auf Wurzel
• Amortisierte Komplexität: Fast O(1)

def union(eltern, rang, i, j):
    ri, rj = finde(eltern, i), finde(eltern, j)
    if ri != rj:
        if rang[ri] < rang[rj]:
            eltern[ri] = rj
        else:
            eltern[rj] = ri
            if rang[ri] == rang[rj]:
                rang[ri] += 1
        return True  # Verbindung war erfolgreich
    return False  # Waren schon verbunden

Union by Rank:

• Kleinerer Baum wird unter größeren gehängt
• Verhindert degenerierte Bäume (lineare Ketten)
• Hält Bäume flach
• return True/False: Zeigt an, ob Verbindung neu war

def zaehle_circuits(eltern, n):
    wurzeln = set()
    for i in range(n):
        wurzeln.add(finde(eltern, i))
    return len(wurzeln)

Netzwerk-Zählung:

• Findet alle eindeutigen Wurzeln
• Anzahl Wurzeln = Anzahl separate Netzwerke

2. Distanz-Berechnung

dosen = [[int(x) for x in dose.strip().split(",")] for dose in aufgabe.zeilen]
distanzen = sorted([(sum((a - b) ** 2 for a, b in zip(dose1, dose2)), idx1, idx2, dose1[0], dose2[0])
                    for (idx1, dose1), (idx2, dose2) in itertools.combinations(enumerate(dosen), 2)])

Logik:

1. Parse Koordinaten: Jede Zeile wird zu Liste von Integers

2. Alle Paare generieren:

   itertools.combinations(enumerate(dosen), 2)

   • enumerate(dosen): (index, koordinaten) Paare
   • combinations(..., 2): Alle 2er-Kombinationen
   • Anzahl: n * (n-1) / 2 Paare

3. Quadrierte Euklidische Distanz:

   sum((a - b) ** 2 for a, b in zip(dose1, dose2))

   • Funktioniert für beliebige Dimensionen
   • Keine Wurzel nötig: Sortierung ist gleich
   • Schneller ohne sqrt()

4. Tuple-Struktur:

   (distanz, idx1, idx2, x1, x2)

   • distanz: Für Sortierung
   • idx1, idx2: Für Union-Find
   • x1, x2: X-Koordinaten für Teil 2

5. Sortierung: Nach Distanz (kürzeste zuerst)

3. Teil 1 - Erste 1000 Verbindungen

n = len(dosen)
eltern = list(range(n))
rang = [0] * n

for distanz, idx1, idx2, x1, x2 in distanzen[:1000]:
    union(eltern, rang, idx1, idx2)

Initialisierung:

• eltern = [0, 1, 2, ...]: Jede Dose ist eigene Wurzel
• rang = [0, 0, 0, ...]: Alle Bäume haben Rang 0

Verbinde 1000 kürzeste Paare:

• Ignoriere ob schon verbunden
• Union-Find verhindert Zyklen automatisch

netzwerke = {}
for i in range(n):
    wurzel = finde(eltern, i)
    netzwerke.setdefault(wurzel, []).append(i)
sortiert = sorted(netzwerke.values(), key=len, reverse=True)
aufgabe.loesung1 = len(sortiert[0]) * len(sortiert[1]) * len(sortiert[2])

Netzwerke gruppieren:

• Dictionary: {wurzel: [dose1, dose2, ...]}
• Alle Dosen mit gleicher Wurzel = ein Netzwerk

3 größte finden:

• Sortiere nach Größe (absteigend)
• Multipliziere Größen der ersten 3

4. Teil 2 - Bis zu einem Netzwerk

for distanz, idx1, idx2, x1, x2 in distanzen[1000:]:
    if union(eltern, rang, idx1, idx2):
        if zaehle_circuits(eltern, n) == 1:
            aufgabe.loesung2 = x1 * x2
            break

Logik:

1. Fahre fort ab Paar 1000: distanzen[1000:]

2. Nur neue Verbindungen: if union(...)

   • Überspringt Paare, die schon im gleichen Netzwerk sind
   • Effizienter als immer zu zählen

3. Prüfe auf Vereinigung: zaehle_circuits(eltern, n) == 1

   • Wenn nur noch 1 Wurzel existiert
   • Alle Dosen sind verbunden

4. Speichere Ergebnis: x1 * x2

   • X-Koordinaten des letzten verbundenen Paares
   • Break sofort

Beispiel-Durchlauf

Eingabe:

0,0
3,0
0,3
6,0

Dosen: [[0,0], [3,0], [0,3], [6,0]]

Distanzen (sortiert):

(9, 0, 1, 0, 3)    # (0,0) - (3,0): dist = 3² = 9
(9, 0, 2, 0, 0)    # (0,0) - (0,3): dist = 3² = 9
(18, 1, 2, 3, 0)   # (3,0) - (0,3): dist = 3² + 3² = 18
(36, 0, 3, 0, 6)   # (0,0) - (6,0): dist = 6² = 36
(45, 1, 3, 3, 6)   # (3,0) - (6,0): dist = 3² = 9 (Fehler im Beispiel)
...

Nach ersten 3 Verbindungen:

• Union(0, 1): Netzwerk {0, 1}
• Union(0, 2): Netzwerk {0, 1, 2}
• Union(1, 3): Netzwerk {0, 1, 2, 3}

Alle verbunden nach 3 Verbindungen (bei nur 4 Dosen).

Komplexität

Distanz-Berechnung:

• Zeit: O(n² * d) wobei n = Anzahl Dosen, d = Dimensionen
• Platz: O(n²) für alle Distanzen

Sortierung:

• Zeit: O(n² log n)

Union-Find Operationen:

• Zeit: O(α(n)) pro Operation (fast konstant)
• α = Inverse Ackermann-Funktion (praktisch ≤ 4)

Teil 1:

• Zeit: O(1000 * α(n) + n) = O(n)
• 1000 Union-Operationen + n Find-Operationen

Teil 2:

• Zeit: O(k * α(n)) wobei k = Anzahl Verbindungen bis Vereinigung
• Schlechtester Fall: O(n * α(n))

Gesamt:

• Zeit: O(n² * d + n² log n)
• Platz: O(n²)

Besonderheiten

Kruskal's Algorithmus:

• Greedy MST-Algorithmus
• Fügt kürzeste Kanten hinzu, die keinen Zyklus bilden
• Union-Find ist perfekt für Zyklus-Erkennung

Quadrierte Distanz:

• Vermeidet teure sqrt() Berechnung
• Sortierung bleibt gleich
• Nur für Distanz-Vergleiche, nicht absolute Werte

Optimale Verbindungs-Anzahl:

• MST mit n Knoten hat genau n-1 Kanten
• Hier: 1000 Kanten für Teil 1, dann weiter für Teil 2

Path Compression:

• Macht wiederholte Finds sehr schnell
• Essentiell für gute Performance

Union by Rank:

• Verhindert degenerierte Bäume
• Zusammen mit Path Compression: Fast O(1)

Warum 1000?

• Puzzle-spezifische Zahl
• Teilt MST-Konstruktion in zwei Phasen
• Teil 1 schaut auf Zwischenstand, Teil 2 auf Vollendung

itertools.combinations:

• Effizient für alle Paare
• Keine Duplikate, keine Selbst-Paare
• Pythonischer als nested loops