rust_algorithms/data_structures/
disjoint_set.rs

1//! Disjoint Set Union (DSU / Union-Find) — "kim kim bilan bir guruhda?".
2
3/// Kesishmaydigan to'plamlar strukturasi: elementlarni guruhlarga birlashtiradi
4/// va "bu ikkovi bir guruhdami?" savoliga deyarli **O(1)** da javob beradi.
5///
6/// **G'oya:** har bir guruh — daraxt, daraxtning ildizi guruh "vakili".
7/// Ikki optimallashtirish uni juda tez qiladi:
8/// 1. **Path compression** (`find` da): yo'ldagi hamma tugunni to'g'ridan-to'g'ri
9///    ildizga ulaymiz — keyingi so'rovlar bir qadamda tugaydi.
10/// 2. **Union by rank**: kichik daraxtni kattasiga ulaymiz — daraxt bo'yi o'smaydi.
11///
12/// Ikkalasi birga — amortizatsiyalangan **O(α(n))**, bu yerda α — teskari Akkerman
13/// funksiyasi. Amalda α(n) ≤ 4 (koinotdagi atomlar soni uchun ham).
14///
15/// **Qayerda ishlatiladi:** Kruskal MST, tarmoqdagi bog'liq komponentalar,
16/// "do'stlar do'stim" tipidagi masalalar, rasm segmentatsiyasi.
17///
18/// # Misol
19/// ```
20/// use rust_algorithms::data_structures::DisjointSet;
21///
22/// let mut ds = DisjointSet::new(5); // 0..4
23/// ds.union(0, 1);
24/// ds.union(3, 4);
25/// assert!(ds.connected(0, 1));
26/// assert!(!ds.connected(1, 3));
27/// assert_eq!(ds.count(), 3);        // {0,1}, {2}, {3,4}
28///
29/// ds.union(1, 4);
30/// assert!(ds.connected(0, 3));
31/// assert_eq!(ds.count(), 2);
32/// ```
33#[derive(Debug, Clone)]
34pub struct DisjointSet {
35    parent: Vec<usize>,
36    rank: Vec<u32>,
37    size: Vec<usize>,
38    count: usize,
39}
40
41impl DisjointSet {
42    /// `n` ta alohida element (`0..n`) bilan boshlaydi.
43    pub fn new(n: usize) -> Self {
44        Self {
45            parent: (0..n).collect(),
46            rank: vec![0; n],
47            size: vec![1; n],
48            count: n,
49        }
50    }
51
52    /// `x` ning guruh vakilini (ildizini) topadi — yo'lni siqish bilan.
53    pub fn find(&mut self, x: usize) -> usize {
54        if self.parent[x] != x {
55            let ildiz = self.find(self.parent[x]);
56            self.parent[x] = ildiz; // path compression
57        }
58        self.parent[x]
59    }
60
61    /// `a` va `b` guruhlarini birlashtiradi.
62    /// Qaytadi: `true` — haqiqatan birlashtirildi, `false` — allaqachon bir guruhda edi.
63    pub fn union(&mut self, a: usize, b: usize) -> bool {
64        let (mut ra, mut rb) = (self.find(a), self.find(b));
65        if ra == rb {
66            return false;
67        }
68        // union by rank: pastroq daraxtni balandrog'iga ulaymiz
69        if self.rank[ra] < self.rank[rb] {
70            std::mem::swap(&mut ra, &mut rb);
71        }
72        self.parent[rb] = ra;
73        self.size[ra] += self.size[rb];
74        if self.rank[ra] == self.rank[rb] {
75            self.rank[ra] += 1;
76        }
77        self.count -= 1;
78        true
79    }
80
81    /// `a` va `b` bir guruhdami?
82    pub fn connected(&mut self, a: usize, b: usize) -> bool {
83        self.find(a) == self.find(b)
84    }
85
86    /// `x` turgan guruhdagi elementlar soni.
87    pub fn size_of(&mut self, x: usize) -> usize {
88        let r = self.find(x);
89        self.size[r]
90    }
91
92    /// Nechta alohida guruh bor.
93    pub fn count(&self) -> usize {
94        self.count
95    }
96
97    /// Umumiy elementlar soni.
98    pub fn len(&self) -> usize {
99        self.parent.len()
100    }
101
102    /// Elementlar bormi?
103    pub fn is_empty(&self) -> bool {
104        self.parent.is_empty()
105    }
106}
107
108#[cfg(test)]
109mod tests {
110    use super::*;
111
112    #[test]
113    fn boshlangich_holat() {
114        let mut ds = DisjointSet::new(10);
115        assert_eq!(ds.count(), 10);
116        for i in 0..10 {
117            assert_eq!(ds.size_of(i), 1);
118            assert!(ds.connected(i, i));
119        }
120    }
121
122    #[test]
123    fn zanjir_birlashtirish() {
124        let mut ds = DisjointSet::new(100);
125        for i in 0..99 {
126            assert!(ds.union(i, i + 1));
127        }
128        assert_eq!(ds.count(), 1);
129        assert_eq!(ds.size_of(0), 100);
130        assert!(ds.connected(0, 99));
131    }
132
133    #[test]
134    fn takroriy_union_false_qaytaradi() {
135        let mut ds = DisjointSet::new(3);
136        assert!(ds.union(0, 1));
137        assert!(!ds.union(1, 0));
138        assert_eq!(ds.count(), 2);
139    }
140
141    #[test]
142    fn ikki_guruh_alohida_qoladi() {
143        let mut ds = DisjointSet::new(6);
144        ds.union(0, 1);
145        ds.union(1, 2);
146        ds.union(3, 4);
147        assert_eq!(ds.size_of(0), 3);
148        assert_eq!(ds.size_of(3), 2);
149        assert_eq!(ds.size_of(5), 1);
150        assert!(!ds.connected(2, 4));
151        assert_eq!(ds.count(), 3);
152    }
153}
rust_algorithms/data_structures/disjoint_set.rs

rust_algorithms/data_structures/
disjoint_set.rs
