Union-Find (Ayrık Küme)

Veri Yapıları O(α(n)) O(n)

Küme ormanı: find köke yürür ve arkasındaki yolu düzleştirir, union düşük rütbeli kökü yükseğin altına asar.

BirleştirmelerBul

1/37

makeSets(8): her eleman rütbesi 0 olan kendi köküdür.

DeğişmezHer eleman kümesinin kökünü gösterir; iki eleman tam olarak aynı kökü paylaştıklarında aynı kümededir.

mevcutkarşılaştıreklesildöndür

union-find.c

int parent[N], rank_[N];
 
void makeSets(int n) {
    for (int i = 0; i < n; i++) {
        parent[i] = i;
        rank_[i] = 0;
    }
}
 
int find(int x) {
    if (parent[x] != x)
        parent[x] = find(parent[x]);   /* compress */
    return parent[x];
}
 
void unionSets(int a, int b) {
    int ra = find(a), rb = find(b);
    if (ra == rb) return;              /* same set */
    if (rank_[ra] < rank_[rb]) {
        parent[ra] = rb;
    } else if (rank_[ra] > rank_[rb]) {
        parent[rb] = ra;
    } else {
        parent[rb] = ra;
        rank_[ra]++;
    }
}

Union-Find (Ayrık Küme) nasıl çalışır?

Her küme bir ağaçtır; kök kümenin temsilcisidir. find(x) köke yürür, union bir kökü diğerinin altına bağlar. Yol sıkıştırma, ziyaret edilen her düğümü doğrudan köke bağlar — kullanım yan etkisi olarak ağaçlar düzleşir.

En iyi durum

Düzleşmiş ağaçlar — find tek sıçrama: fiilen O(1).

En kötü durum

Rütbeye göre birleştirme + yol sıkıştırmayla: amorti O(α(n)) — ters Ackermann, pratikte ≤ 4.

Ne zaman kullanılır?

Dinamik bağlantılılık: Kruskal MST, döngü tespiti, eşdeğer öğeleri gruplama.