Disjoint Set Union (DSU) – teorija i osnovne operacije

U ovoj lekciji upoznaćemo se sa strukturom podataka Disjoint Set Union (DSU), poznatom i kao Union-Find. Ona se koristi za efikasno praćenje skupa elemenata koji su podeljeni u međusobno disjunktne (nepreklapajuće) podskupove.

Ova struktura se često koristi u algoritmima koji rade sa povezanim komponentama grafa, naročito u Kruškalovom algoritmu za pronalaženje minimalnog razapinjućeg stabla (MST – Minimum Spanning Tree).

Osnovna ideja

DSU omogućava sledeće dve osnovne operacije:

find(x) – pronalazi predstavnika (korenski element) skupa kojem element x pripada.
unite(a, b) – spaja dva skupa kojima pripadaju elementi a i b.

Ideja je da svaki element pokazuje na svog „roditelja“. Ako element pokazuje sam na sebe, on je koren svog skupa. Kada želimo da spojimo dva skupa, samo povezujemo njihove korene. Da bi operacije bile brže, koristi se:

Path compression – skraćuje putanju do korena prilikom poziva find().
Union by rank/size – uvek se manji skup pridružuje većem.

Implementacija DSU strukture


#include <iostream>
#include <vector>
using namespace std;

struct DSU {
    vector<int> parent, size;

    DSU(int n) {
        parent.resize(n);
        size.resize(n, 1);
        for (int i = 0; i < n; i++)
            parent[i] = i;
    }

    int find(int x) {
        if (x == parent[x])
            return x;
        return parent[x] = find(parent[x]); // path compression
    }

    void unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a != b) {
            if (size[a] < size[b])
                swap(a, b);
            parent[b] = a;
            size[a] += size[b];
        }
    }
};

int main() {
    DSU dsu(5);

    dsu.unite(0, 1);
    dsu.unite(3, 4);

    cout << "Find(1): " << dsu.find(1) << endl;
    cout << "Find(4): " << dsu.find(4) << endl;

    dsu.unite(1, 3);
    cout << "Find(0) after merging: " << dsu.find(0) << endl;

    return 0;
}

Kruškalov algoritam i veza sa DSU

Kruškalov algoritam je algoritam koji pronalazi minimalno razapinjuće stablo (MST) u povezanom, neusmerenom i ponderisanom grafu. Ideja algoritma je sledeća:

Sortirati sve grane grafa po težini (od najmanje ka najvećoj).
Prolaziti redom kroz grane i dodavati granu u MST samo ako ne formira ciklus.
Proveru da li grana formira ciklus vršimo pomoću DSU strukture.

Ako se krajevi grane nalaze u različitim skupovima (tj. find(u) != find(v)), grana se dodaje u MST i skupovi se spajaju pomoću unite(u, v).

Implementacija Kruškalovog algoritma


#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Edge {
    int u, v, w;
};

struct DSU {
    vector<int> parent, size;
    DSU(int n) {
        parent.resize(n);
        size.resize(n, 1);
        for (int i = 0; i < n; i++)
            parent[i] = i;
    }
    int find(int x) {
        if (x == parent[x]) return x;
        return parent[x] = find(parent[x]);
    }
    void unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a != b) {
            if (size[a] < size[b]) swap(a, b);
            parent[b] = a;
            size[a] += size[b];
        }
    }
};

int main() {
    int n = 4;
    vector<Edge> edges = {
        {0, 1, 10},
        {0, 2, 6},
        {0, 3, 5},
        {1, 3, 15},
        {2, 3, 4}
    };

    sort(edges.begin(), edges.end(), [](Edge a, Edge b) {
        return a.w < b.w;
    });

    DSU dsu(n);
    int mst_weight = 0;

    cout << "Edges in the Minimum Spanning Tree:\n";
    for (auto e : edges) {
        if (dsu.find(e.u) != dsu.find(e.v)) {
            dsu.unite(e.u, e.v);
            mst_weight += e.w;
            cout << e.u << " - " << e.v << " (" << e.w << ")\n";
        }
    }

    cout << "Total weight of MST: " << mst_weight << endl;
    return 0;
}

Zaključak

Struktura Disjoint Set Union omogućava efikasno spajanje skupova i proveru pripadnosti elemenata istom skupu, što je ključno za mnoge algoritme nad grafovima. U kombinaciji sa Kruškalovim algoritmom, DSU omogućava izgradnju minimalnog razapinjućeg stabla u vremenu blizu linearnog u odnosu na broj grana.

Vizualizacija rada DSU strukture (korak po korak)

Da bismo bolje razumeli kako Disjoint Set Union (DSU) struktura funkcioniše iznutra, pogledajmo jednostavan primer i prikažimo kako se elementi grupišu i kako se koristi path compression (kompresija putanje).

Primer: Spajanje skupova korak po korak

Pretpostavimo da imamo 6 elemenata: 0, 1, 2, 3, 4, 5. Na početku, svaki element je svoj roditelj:


// Početno stanje (svaki element je svoj roditelj):
Roditelj: [0, 1, 2, 3, 4, 5]

Sada spajamo neke skupove:


unite(0, 1)   →  spajamo skupove koji sadrže 0 i 1
unite(2, 3)   →  spajamo skupove koji sadrže 2 i 3
unite(4, 5)   →  spajamo skupove koji sadrže 4 i 5

Nakon ovih operacija, niz roditelja može izgledati ovako:


Roditelj: [0, 0, 2, 2, 4, 4]

To znači:

Elementi 0 i 1 su u istom skupu (korenski element je 0)
Elementi 2 i 3 su u istom skupu (korenski element je 2)
Elementi 4 i 5 su u istom skupu (korenski element je 4)

Spajanje većih skupova

Sada izvršavamo unite(1, 3). Pre spajanja:


find(1) = 0
find(3) = 2

Pošto imaju različite korene (0 i 2), DSU ih spaja:


Roditelj: [0, 0, 0, 2, 4, 4]

Nakon kompresije putanje, elementi 2 i 3 takođe direktno pokazuju na 0:


// Nakon find(3) sa path compression:
Roditelj: [0, 0, 0, 0, 4, 4]

Sada svi elementi {0, 1, 2, 3} pripadaju istom skupu sa korenom 0.

Tekstualni dijagram

Evo jednostavnog prikaza spajanja:


// Početno stanje:
0   1   2   3   4   5
|   |   |   |   |   |
(0) (1) (2) (3) (4) (5)

// Nakon unite(0,1), unite(2,3), unite(4,5):
0 → 1     2 → 3     4 → 5

// Nakon unite(1,3):
0 → 1, 2 → 3, a root(0) se povezuje sa root(2)
Konačna struktura:
0
├── 1
├── 2
│   └── 3
4
└── 5

Kada kasnije pozovemo find(3), kompresija putanje čini da 3 direktno pokazuje na 0:


// Nakon kompresije putanje:
0 → {1, 2, 3}
4 → {5}

Zašto je path compression koristan?

Bez kompresije putanje, svaka find() operacija mogla bi da prolazi kroz dugačak lanac roditelja. Kompresija putanje čini da svi čvorovi direktno pokazuju na koren, čime se struktura "izravnava". Tako sledeći pozivi find() i unite() postaju skoro konstantnog vremena.

Intuitivno objašnjenje

Možemo zamisliti svaku grupu kao malo drvo. Kada se dva drveta spoje, jedan koren postaje dete drugog. Path compression znači da prilikom traženja korena, "ispravljamo" stablo tako da svi čvorovi budu bliže korenu, što značajno ubrzava buduće pretrage.

Vizuelno objašnjenje rada DSU

Na slikama 1 prikazana je vizualizacija strukture podataka Disjoint Set Union (DSU) ili Union-Find, koja služi za efikasno upravljanje skupovima koji se ne preklapaju. Svaki element pripada nekom skupu, a svi skupovi su međusobno disjunktni (ne dele nijedan zajednički element).

U početnom stanju, svaki element je samostalan i ima samog sebe za roditelja. To znači da postoji onoliko skupova koliko ima elemenata — svaki element je koren svog stabla.

1. Početno stanje

Na početku, svi čvorovi (npr. 1, 2, 3, 4, 5, 6, 7, 8) su nezavisni:


1   2   3   4   5   6   7   8

U kodu, ovo se obično inicijalizuje tako što se za svaki element postavi:


for (int i = 1; i <= n; i++) parent[i] = i;

Tada svaka promenljiva parent[i] pokazuje na sebe.

2. Spajanje skupova (union)

Kada izvršimo operacije union(1, 2) i union(2, 3), čvorovi 1, 2 i 3 se spajaju u jedan skup. Koren tog skupa je element 1.


   1
  / \
 2   3

U memoriji to znači: parent[2] = 1 i parent[3] = 1.

3. Formiranje više grupa

Ako zatim izvršimo union(4, 5) i union(6, 7), nastaju odvojene grupe (stabla). Svaka grupa ima svoj koren — predstavnika.


   1        4        6       8
  / \      /         \      
 2   3    5           7

4. Spajanje postojećih grupa

Kada pozovemo union(3, 4), DSU pronalazi korene elemenata 3 i 4. Koreni su 1 i 4, i tada se grupe spajaju u jednu.

Time elementi 1, 2, 3, 4 i 5 postaju deo istog skupa.

5. Kompresija putanje (path compression)

Pri pozivu find(5), algoritam prelazi putanju 5 → 4 → 1 i vraća 1 kao koren. Zatim ažurira sve roditelje na tom putu da direktno pokazuju na koren (1), čime se smanjuje visina stabla.


// Pre kompresije: 5 → 4 → 1
// Posle kompresije:
parent[5] = 1;

6. Završno stanje

Na kraju, imamo dve glavne grupe:


   1              6
  /|\             \
 2 3 4             7
    |
    5

Grupa 1 sadrži elemente {1, 2, 3, 4, 5}, a grupa 6 sadrži {6, 7, 8}.

7. Zaključak

DSU koristi stabla za predstavljanje skupova i omogućava brzo spajanje i pronalaženje predstavnika. Zahvaljujući kompresiji putanje i spajanju po rangu, DSU operacije se izvršavaju gotovo u konstantnom vremenu.

Slika 1: Vizualizacija operacija u DSU (find i union)

Primene DSU strukture i implementacije u drugim jezicima

Do sada smo prikazali Disjoint Set Union (DSU) u kontekstu Kruškalovog algoritma za izgradnju minimalnog razapinjućeg stabla (MST). Međutim, DSU je mnogo šire primenljiva struktura podataka — koristi se u problemima gde je potrebno efikasno pratiti povezanost elemenata.

1. Šire primene DSU strukture

DSU se koristi u brojnim algoritmima i scenarijima, među kojima su:

Dinamičko spajanje komponenti grafa — kada se veze između čvorova dodaju postepeno, a potrebno je proveriti da li su dva čvora povezana.
Proveravanje ciklusa u neusmerenom grafu — DSU može da otkrije kada nova grana stvara ciklus.
Offline upiti o povezivosti — u problemima gde se upiti postavljaju unapred, pa se odgovori dobijaju unazad korišćenjem DSU-a.
Detekcija zajednica u mrežama — za grupisanje elemenata u klastere.
Dinamički problemi na mrežama — kao što su „dinamičko dodavanje puteva“ ili „brisanje grana“ uz ponovnu proveru povezanosti.

Ova struktura podataka je temelj mnogih naprednih algoritama iz oblasti grafova, mreža i teorije skupova.

2. Pseudokod DSU strukture

Bez obzira na programski jezik, logika DSU strukture se može opisati sledećim pseudokodom:


procedure make_set(x):
    parent[x] = x
    rank[x] = 0

function find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])   // path compression
    return parent[x]

procedure union(x, y):
    rootX = find(x)
    rootY = find(y)
    if rootX == rootY:
        return
    if rank[rootX] < rank[rootY]:
        parent[rootX] = rootY
    else if rank[rootX] > rank[rootY]:
        parent[rootY] = rootX
    else:
        parent[rootY] = rootX
        rank[rootX] = rank[rootX] + 1

3. Implementacija u Python-u

Python omogućava jednostavnu i čitljivu implementaciju DSU strukture:


class DSU:
    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.rank = [0] * 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):
        xr, yr = self.find(x), self.find(y)
        if xr == yr:
            return
        if self.rank[xr] < self.rank[yr]:
            self.parent[xr] = yr
        elif self.rank[xr] > self.rank[yr]:
            self.parent[yr] = xr
        else:
            self.parent[yr] = xr
            self.rank[xr] += 1

4. Implementacija u Javi

Evo jednostavne implementacije DSU strukture u Java jeziku:


class DSU {
    int[] parent, rank;

    DSU(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }

    int find(int x) {
        if (parent[x] != x)
            parent[x] = find(parent[x]); // path compression
        return parent[x];
    }

    void union(int x, int y) {
        int xr = find(x), yr = find(y);
        if (xr == yr) return;
        if (rank[xr] < rank[yr]) parent[xr] = yr;
        else if (rank[xr] > rank[yr]) parent[yr] = xr;
        else {
            parent[yr] = xr;
            rank[xr]++;
        }
    }
}

5. Poređenje jezika i konceptualno značenje

Bez obzira da li se koristi C++, Python ili Java, osnovni principi su isti:

Svaki element ima roditelja i (opciono) rang koji predstavlja visinu stabla.
find() pronalazi koren skupa uz kompresiju putanje.
union() spaja dva skupa po rangu ili veličini.

Zahvaljujući ovim optimizacijama, DSU se može koristiti i u složenim problemima gde se odnosi između elemenata često menjaju, kao što su dinamičke mreže, algoritmi na grafovima i sistemi klasterizacije.