Struct DisjointSet 

pub struct DisjointSet { /* private fields */ }

Kesishmaydigan to’plamlar strukturasi: elementlarni guruhlarga birlashtiradi va “bu ikkovi bir guruhdami?” savoliga deyarli O(1) da javob beradi.

G’oya: har bir guruh — daraxt, daraxtning ildizi guruh “vakili”. Ikki optimallashtirish uni juda tez qiladi:

1. Path compression (find da): yo’ldagi hamma tugunni to’g’ridan-to’g’ri ildizga ulaymiz — keyingi so’rovlar bir qadamda tugaydi.
2. Union by rank: kichik daraxtni kattasiga ulaymiz — daraxt bo’yi o’smaydi.

Ikkalasi birga — amortizatsiyalangan O(α(n)), bu yerda α — teskari Akkerman funksiyasi. Amalda α(n) ≤ 4 (koinotdagi atomlar soni uchun ham).

Qayerda ishlatiladi: Kruskal MST, tarmoqdagi bog’liq komponentalar, “do’stlar do’stim” tipidagi masalalar, rasm segmentatsiyasi.

Misol

use rust_algorithms::data_structures::DisjointSet;

let mut ds = DisjointSet::new(5); // 0..4
ds.union(0, 1);
ds.union(3, 4);
assert!(ds.connected(0, 1));
assert!(!ds.connected(1, 3));
assert_eq!(ds.count(), 3);        // {0,1}, {2}, {3,4}

ds.union(1, 4);
assert!(ds.connected(0, 3));
assert_eq!(ds.count(), 2);

Implementations

impl DisjointSet

pub fn new(n: usize) -> Self

n ta alohida element (0..n) bilan boshlaydi.

pub fn find(&mut self, x: usize) -> usize

x ning guruh vakilini (ildizini) topadi — yo’lni siqish bilan.

pub fn union(&mut self, a: usize, b: usize) -> bool

a va b guruhlarini birlashtiradi. Qaytadi: true — haqiqatan birlashtirildi, false — allaqachon bir guruhda edi.

pub fn connected(&mut self, a: usize, b: usize) -> bool

a va b bir guruhdami?

pub fn size_of(&mut self, x: usize) -> usize

x turgan guruhdagi elementlar soni.

pub fn count(&self) -> usize

Nechta alohida guruh bor.

pub fn len(&self) -> usize

Umumiy elementlar soni.

pub fn is_empty(&self) -> bool

Elementlar bormi?

Trait Implementations

impl Clone for DisjointSet

fn clone(&self) -> DisjointSet

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for DisjointSet

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.