0Pricing
DSA Interview Prep · Lekcja

DSU z kompresją ścieżek

Implementować find z kompresją ścieżek, aby wszystkie wierzchołki na ścieżce wskazywały bezpośrednio na korzeń, uzyskując zamortyzowany czas find bliski O(1)

DSU z kompresją ścieżek to bezpłatna lekcja DSA Interview Prep na CoddyKit. To lekcja 1 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej DSA Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.

Czym jest Disjoint Set Union?

Disjoint Set Union (DSU), nazywany także Union-Find, to struktura danych przechowująca kolekcję rozłącznych (nieprzecinających się) zbiorów. Obsługuje dwie podstawowe operacje: find (do którego zbioru należy element x?) oraz union (połącz zbiory zawierające x i y). DSU doskonale nadaje się do problemów dynamicznej spójności, w których grupy z czasem się łączą, ale nigdy się nie rozdzielają.

Każdy element początkowo stanowi osobny zbiór. Podczas przetwarzania krawędzi lub relacji łączymy ze sobą zbiory. Wyzwaniem jest wydajne wykonywanie tych operacji — naiwne implementacje mają złożoność O(n) na operację, ale dzięki optymalizacjom zbliżamy się do zamortyzowanej złożoności O(1).

# Naive DSU without optimisations
class DSU:
    def __init__(self, n):
        self.parent = list(range(n))  # each node is its own parent

    def find(self, x):
        while self.parent[x] != x:
            x = self.parent[x]
        return x

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px != py:
            self.parent[px] = py

Problem z naiwną operacją find

W naiwnym DSU operacja find(x) przechodzi w górę łańcucha rodziców, aż dotrze do węzła wskazującego na samego siebie (korzenia). Jeśli drzewo jest zrównoważone, zajmuje to O(log n). Jeśli jednak zawsze łączymy drzewa, umieszczając drugi korzeń pod pierwszym, możemy utworzyć łańcuch (drzewo zdegenerowane) długości n, przez co każda operacja find będzie mieć złożoność O(n).

Rozważmy kolejno wykonywane operacje łączenia 0→1→2→3→4. Operacja find dla węzła 0 musi przejść przez cały łańcuch. Dzięki kompresji ścieżki eliminujemy ten problem, sprawiając, że każdy odwiedzony węzeł wskazuje bezpośrednio na korzeń już podczas samej operacji find.

# Worst case without compression: a chain
# parent = [1, 2, 3, 4, 4]  => find(0) takes 4 steps
# After path compression: parent = [4, 4, 4, 4, 4]  => find(0) takes 1 step

parent = [1, 2, 3, 4, 4]
print('Before:', parent)
# Simulate find(0) with naive approach
x = 0
steps = 0
while parent[x] != x:
    x = parent[x]
    steps += 1
print('Root:', x, 'Steps taken:', steps)

Kompresja ścieżki: rekurencyjna jednoprzebiegowa

Kompresja ścieżki modyfikuje operację find tak, aby po znalezieniu korzenia każdy węzeł leżący na ścieżce wskazywał na niego bezpośrednio. Przyszłe operacje find dla tych węzłów mają złożoność O(1). Wersja rekurencyjna osiąga to w elegancki sposób w jednym przebiegu.

Kluczowa obserwacja jest następująca: po zwróceniu korzenia przez wywołanie rekurencyjne przed zakończeniem operacji ustawiamy self.parent[x] = root. W ten sposób spłaszczamy drzewo — wszystkie węzły na przeszukiwanej ścieżce wskazują teraz bezpośrednio na korzeń. Nie zmienia to zbioru, do którego należy węzeł; jedynie skraca ścieżki wyszukiwania przy kolejnych operacjach.

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # path compression
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px != py:
            self.parent[px] = py

dsu = DSU(5)
dsu.union(0, 1)
dsu.union(1, 2)
dsu.union(2, 3)
print('Root of 0:', dsu.find(0))
print('Parent array after compression:', dsu.parent)

Kompresja ścieżki: iteracyjna dwuprzebiegowa

Iteracyjna wersja kompresji ścieżki korzysta z dwóch przebiegów: w pierwszym przechodzi w górę, aby znaleźć korzeń, a w drugim ponownie odwiedza każdy węzeł na ścieżce i bezpośrednio ustawia jego rodzica na korzeń. Pozwala to uniknąć narzutu stosu wywołań rekurencyjnych i jest bezpieczne nawet dla bardzo głębokich drzew, gdy zbliżamy się do limitu rekurencji w Pythonie.

W podejściu rekurencyjnym i iteracyjnym poprawność pozostaje bez zmian — find nadal zwraca ten sam korzeń. Jedyną różnicą jest aktualizowanie wskaźników rodziców jako efekt uboczny, dzięki czemu wszystkie przyszłe operacje find dla tych węzłów mają złożoność O(1).

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))

    def find(self, x):
        root = x
        while self.parent[root] != root:
            root = self.parent[root]          # first pass: find root
        while self.parent[x] != root:
            nxt = self.parent[x]
            self.parent[x] = root             # second pass: compress
            x = nxt
        return root

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px != py:
            self.parent[px] = py
            return True
        return False  # already connected

dsu = DSU(6)
for a, b in [(0,1),(1,2),(2,3),(3,4)]:
    dsu.union(a, b)
print('Parent before find(0):', dsu.parent[:])
dsu.find(0)
print('Parent after  find(0):', dsu.parent[:])

Zamortyzowana złożoność kompresji ścieżki

Sama kompresja ścieżki zapewnia zamortyzowany czas O(log n) na operację w całej sekwencji m operacji. Pierwsza operacja find może być kosztowna, jeśli trzeba przejść przez łańcuch, ale spłaszcza go, dzięki czemu każda kolejna operacja find dla tych węzłów ma złożoność O(1). Całkowity koszt pracy rozkłada się na wiele operacji.

Formalna analiza wykorzystuje metodę funkcji potencjału: potencjał DSU zmniejsza się za każdym razem, gdy skraca się ścieżka od węzła do rodzica, a ten spadek pokrywa koszt przejścia. Bez łączenia według rangi sama kompresja ścieżki daje zamortyzowaną złożoność O(log n) — już ogromną poprawę względem naiwnego O(n).

# Demonstrating amortised benefit
import time

def build_chain(n):
    parent = list(range(n))
    for i in range(n - 1):
        parent[i] = i + 1  # chain: 0->1->2->...->n-1
    return parent

n = 1000
parent = build_chain(n)

# First find on a chain: visits n nodes
x = 0
root = x
while parent[root] != root:
    root = parent[root]
# Compress
while parent[x] != root:
    nxt = parent[x]; parent[x] = root; x = nxt
print('After first find, parent[0]:', parent[0])  # should be n-1
print('Second find cost: O(1) since parent[0] is now the root')

Liczba spójnych składowych

Jednym z typowych zastosowań DSU jest zliczanie spójnych składowych grafu. Inicjalizujemy licznik components wartością n (po jednej składowej na węzeł). Każda pomyślna operacja union (połączenie dwóch różnych zbiorów) zmniejsza licznik o 1. Na końcu licznik zawiera liczbę odrębnych składowych.

Jest to wydajniejsze niż wykonywanie BFS lub DFS dla zapytań o spójność, szczególnie gdy krawędzie pojawiają się stopniowo (online). DSU przetwarza każdą krawędź w czasie bliskim O(1) w ujęciu zamortyzowanym, niezależnie od momentu jej dodania.

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.components = n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        self.parent[px] = py
        self.components -= 1
        return True

dsu = DSU(7)
edges = [(0,1),(1,2),(3,4),(5,6)]
for u, v in edges:
    dsu.union(u, v)
print('Components:', dsu.components)  # 4: {0,1,2}, {3,4}, {5,6}, {6 alone was merged}
# Node 6 is alone => 4 total: {0,1,2},{3,4},{5,6},{6} wait
# Let me recalculate: 7 nodes, 4 edges merged 4 pairs => 7-4=3... no
# {0,1,2} one union, {3,4} one, {5,6} one => 7-3=4 components
print('Expected: 4')

DSU w zadaniach grafowych: liczba prowincji

Problem Number of Provinces zawiera macierz sąsiedztwa n×n i wymaga obliczenia, ile istnieje grup miast połączonych bezpośrednio lub pośrednio. Jest to dokładnie problem zliczania spójnych składowych, który DSU rozwiązuje w przejrzysty sposób. Iterujemy po wszystkich parach (i, j), dla których isConnected[i][j] == 1, i wywołujemy union(i, j).

Po przetworzeniu wszystkich połączeń wartość dsu.components jest odpowiedzią. To prostsze i szybsze rozwiązanie niż uruchamianie BFS z każdego nieodwiedzonego węzła, a ponadto bezpośrednio obsługuje reprezentację macierzową bez konieczności wcześniejszego tworzenia listy sąsiedztwa.

def find_provinces(isConnected):
    n = len(isConnected)
    parent = list(range(n))

    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    def union(x, y):
        px, py = find(x), find(y)
        if px != py:
            parent[px] = py
            return True
        return False

    count = n
    for i in range(n):
        for j in range(i + 1, n):
            if isConnected[i][j] == 1:
                if union(i, j):
                    count -= 1
    return count

matrix = [[1,1,0],[1,1,0],[0,0,1]]
print(find_provinces(matrix))  # 2: cities {0,1} and {2}

Warianty kompresji ścieżki: połówkowanie

Oprócz kompresji dwuprzebiegowej istnieje prostszy wariant jednoprzebiegowy nazywany połówkowaniem ścieżki: podczas przechodzenia w górę łańcucha sprawiamy, że każdy węzeł wskazuje na swojego dziadka, a nie rodzica. Skraca to ścieżkę o połowę przy każdym przejściu, bez drugiego przebiegu, i w połączeniu z łączeniem według rangi zapewnia tę samą zamortyzowaną złożoność O(alpha(n)).

Połówkowanie ścieżki jest często preferowane w programowaniu konkursowym, ponieważ sprowadza się do jednej prostej pętli i nie wymaga ani rekurencji, ani drugiego przejścia. Każdy krok wykonuje self.parent[x] = self.parent[self.parent[x]]; x = self.parent[x].

class DSUHalving:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]  # point to grandparent
            x = self.parent[x]
        return x

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return True

dsu = DSUHalving(8)
for u, v in [(0,1),(2,3),(4,5),(6,7),(0,2),(4,6),(0,4)]:
    dsu.union(u, v)
print('All in one component:', dsu.find(0) == dsu.find(7))

Sprawdzanie spójności po operacjach union

Aby sprawdzić, czy dwa węzły są połączone (czy należą do tej samej składowej), wywołaj find(x) == find(y). Jeśli oba wywołania zwrócą ten sam korzeń, węzły należą do tej samej składowej. Jest to zapytanie o spójność, które dzięki kompresji ścieżki działa w czasie bliskim O(1) w ujęciu zamortyzowanym.

W zadaniach rekrutacyjnych zapytania o spójność często przeplatają się z operacjami union. DSU obsługuje oba rodzaje operacji online — można wykonywać operacje union i zapytania naprzemiennie, w dowolnej kolejności. To odróżnia DSU od algorytmów dla grafów statycznych, takich jak BFS/DFS, które trzeba uruchamiać ponownie po każdej zmianie struktury.

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px != py:
            self.parent[px] = py

    def connected(self, x, y):
        return self.find(x) == self.find(y)

dsu = DSU(10)
dsu.union(0, 3)
dsu.union(3, 7)
dsu.union(1, 5)
print(dsu.connected(0, 7))   # True: 0-3-7
print(dsu.connected(0, 5))   # False: different components
print(dsu.connected(1, 5))   # True: 1-5

Typowe pułapki w implementacji DSU

Częstym błędem jest wywołanie find, a następnie nieprawidłowa modyfikacja parent. Zawsze wywołuj find dla obu elementów przed sprawdzeniem równości — w przeciwnym razie możesz nieprawidłowo porównać węzeł z jego własnym korzeniem. Inną pułapką jest zapomnienie, że operacja union powinna nic nie robić, gdy oba elementy mają już wspólny korzeń.

W Pythonie limit głębokości rekurencji (domyślnie 1000) może powodować błąd RecursionError dla dużych łańcuchów przy rekurencyjnej wersji find. Można użyć iteracyjnej wersji dwuprzebiegowej, zwiększyć limit za pomocą sys.setrecursionlimit albo zastosować iteracyjne połówkowanie ścieżki, aby całkowicie uniknąć głębokiej rekurencji.

import sys
sys.setrecursionlimit(10000)  # needed for large recursive DSU

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))

    def find(self, x):
        # Safe iterative path compression
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
        while self.parent[x] != root:
            nxt = self.parent[x]
            self.parent[x] = root
            x = nxt
        return root

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False  # already same component — do nothing
        self.parent[px] = py
        return True

dsu = DSU(5)
print(dsu.union(0, 1))  # True: merged
print(dsu.union(0, 1))  # False: already merged — no double-counting

Śledzenie rozmiarów w DSU

W niektórych zadaniach potrzebny jest rozmiar każdej składowej, a nie tylko jej korzeń. Dodaj tablicę size zainicjalizowaną samymi jedynkami. Podczas łączenia dwóch składowych dodaj rozmiar mniejszego korzenia do większego korzenia. Umożliwia to wykonywanie zapytań o rozmiar składowej w czasie O(1) po każdej operacji union.

Śledzenie rozmiarów jest również podstawą łączenia według rozmiaru (alternatywy dla łączenia według rangi): zawsze dołączamy mniejsze drzewo do korzenia większego drzewa. Gwarantuje to, że wysokość drzewa pozostaje na poziomie O(log n), zapewniając taką samą gwarancję asymptotyczną jak łączenie według rangi.

class DSUWithSize:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return
        if self.size[px] < self.size[py]:
            px, py = py, px           # attach smaller under larger
        self.parent[py] = px
        self.size[px] += self.size[py]

    def get_size(self, x):
        return self.size[self.find(x)]

dsu = DSUWithSize(6)
for u, v in [(0,1),(1,2),(3,4)]:
    dsu.union(u, v)
print('Size of component containing 0:', dsu.get_size(0))  # 3
print('Size of component containing 3:', dsu.get_size(3))  # 2
print('Size of component containing 5:', dsu.get_size(5))  # 1

Szybki test

Sprawdź swoją wiedzę na temat zagadnień z kursu Data Structures & Algorithms — Coding Interview Prep omówionych w tej lekcji.

Podsumowanie lekcji

W tej lekcji poznali Państwo następujące zagadnienia: DSU zarządza rozłącznymi zbiorami za pomocą operacji find i union, kompresja ścieżki spłaszcza drzewo, kierując wszystkie odwiedzone węzły bezpośrednio do korzenia, a to zapewnia zamortyzowaną wydajność operacji find bliską O(1). Następnie omówimy łączenie według rangi, które od góry zapobiega nadmiernemu wzrostowi drzew i pozwala osiągnąć ograniczenie wyznaczone przez odwrotną funkcję Ackermanna.

Często zadawane pytania

Czy lekcja „DSU z kompresją ścieżek” jest bezpłatna?

Tak — pełny tekst „DSU z kompresją ścieżek” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu DSA Interview Prep, przejdź na CoddyKit PRO. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.

Co nauczysz się w „DSU z kompresją ścieżek”?

Implementować find z kompresją ścieżek, aby wszystkie wierzchołki na ścieżce wskazywały bezpośrednio na korzeń, uzyskując zamortyzowany czas find bliski O(1) Ćwiczysz DSA Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.

Czy potrzebuję doświadczenia, aby zacząć DSA Interview Prep?

Nie wymagamy żadnego doświadczenia. DSA Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 1 z 4.

Ile czasu zajmuje lekcja „DSU z kompresją ścieżek”?

Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.

Czy mogę pisać i uruchamiać kod w tej lekcji DSA Interview Prep?

Tak. Każda lekcja DSA Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.

Wszystkie lekcje w tym kursie

  1. DSU z kompresją ścieżek
  2. Łączenie według rangi i ograniczenie odwrotną funkcją Ackermanna
  3. Nadmiarowa krawędź i wykrywanie cykli
  4. Scalanie kont i spójne składowe
← Powrót do DSA Interview Prep