Kalıp #19

Union Find

İleri

Dinamik bağlanırlık: bileşenleri birleştir, aynı küme sorgusunu hızlı yap.

Ne zaman kullanılır

Elemanların çevrimiçi birleşimleri ve sık 'a ile b bağlı mı?' sorguları veya birleşmeler sonrası bileşen sayımı.

Tanıma ipuçları

İl sayısı / geçerli ağaç graf
Hesap birleştirme / gereksiz bağlantı
Rank ile union + path compression

Yaygın tuzaklar

Path compression veya rank ile union unutmak (yavaş zincirler)
1-index vs 0-index parent
Zaten bağlıyı kontrol etmeden union (döngü tespitini kaçır)

90 saniyelik tanıma egzersizi

Hangisi en iyi uyuyor?

İl sayısı / geçerli ağaç graf
Hesap birleştirme / gereksiz bağlantı
Rank ile union + path compression

GreedyLinked List ManipulationUnion FindFark Dizisi

Etkileşimli

Zihinsel model

Değişmezin tam adım adım anlatımı. Duraklat, noktalara tıkla veya ← → kullan. Her adımı kendi cümlelerinle anlatmayı hedefle.

Adım 1 / 8

components = 5

Beş eleman; her biri kendi ebeveyni.

Nasıl düşünülür

Her eleman bir parent’a işaret eder; kökler bileşenleri temsil eder. find yolları düzleştirir; union kökleri bağlar (rank/size ile). Union öncesi find(a)==find(b) ise kenar döngü yaratır.

Şablon şekilleri

Şekil	Temel hamle	Notlar
Bağlanırlık	union + find	Bileşen sayısı
Yönsüz döngü	Aynı kökse atla	Gereksiz kenar
Ağırlıklı / öznitelik	Kökte ekstra sakla	Hesap birleştir

Karmaşıklık temeli

Path compression + rank ile işlem başına yaklaşık O(α(n)). Alan O(n).

Şablondan probleme

parent[i]=i; rank[i]=0; components=n.
Path compression ile find.
union: küçük rank’ı büyüğün altına bağla; birleştiyse components–.
Bağlılık sorgusu find eşitliğiyle.

Şablon

TypeScript, Python ve C#’te aynı iskelet. Değişmezi uyarla; yapıyı koru.

Union Find · Şablon

/** Union-Find template: path compression + union by rank. */
export class UnionFind {
  parent: number[];
  rank: number[];
  components: number;
  constructor(n: number) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank = new Array(n).fill(0);
    this.components = n;
  }
  find(x: number): number {
    if (this.parent[x] !== x) this.parent[x] = this.find(this.parent[x]!);
    return this.parent[x]!;
  }
  union(a: number, b: number): boolean {
    let ra = this.find(a), rb = this.find(b);
    if (ra === rb) return false;
    if (this.rank[ra]! < this.rank[rb]!) [ra, rb] = [rb, ra];
    this.parent[rb] = ra;
    if (this.rank[ra] === this.rank[rb]) this.rank[ra]!++;
    this.components--;
    return true;
  }
}

/** Union-Find template: path compression + union by rank. */
export class UnionFind {
  parent: number[];
  rank: number[];
  components: number;
  constructor(n: number) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank = new Array(n).fill(0);
    this.components = n;
  }
  find(x: number): number {
    if (this.parent[x] !== x) this.parent[x] = this.find(this.parent[x]!);
    return this.parent[x]!;
  }
  union(a: number, b: number): boolean {
    let ra = this.find(a), rb = this.find(b);
    if (ra === rb) return false;
    if (this.rank[ra]! < this.rank[rb]!) [ra, rb] = [rb, ra];
    this.parent[rb] = ra;
    if (this.rank[ra] === this.rank[rb]) this.rank[ra]!++;
    this.components--;
    return true;
  }
}

Yol

Yola başla Problem tarayıcısında gör →

#ProblemTürZorlukBitti