Кесилишпеген көптүктөр системасы (DSU)
Кесилишпеген көптүктөр системасы: жолдорду кысуу менен find жана union — дээрлик O(1).
Маселе: элементтер топторго биригет, жана «a менен b бир топтобу?» жана «a менен b топторун бириктир» суроолоруна тез жооп берүү керек. Жөнөкөй жол — жай; DSU (Disjoint Set Union) эки операцияны тең дээрлик O(1) убакытта жасайт.
Идея: ар бир топ — дарак, топтун өкүлү — тамыр. find(v) тамырга чейин көтөрүлөт; union бир тамырды экинчисине илет.
Эки эвристика структураны чагылгандай тез кылат:
• жолдорду кысуу: тамырга бара жатып бардык чокуларды дароо тамырга кайра илебиз;
• ранг боюнча бириктирүү: кичине дарак чоңуна илинет.
DSU. Киргизиңиз: 5 5, андан кийин суроолор: union 1 2 / union 3 4 / check 1 3 / union 2 3 / check 1 4
Мисалды иштетиңиз: union 1 2 жана union 3 4 кийин 1 жана 3 чокулары ар башка топтордо (NO), union 2 3 кийин — бир топто (YES).
parent[v] = find(parent[v]) сабы — так ошол жолду кысуу: рекурсиядан кайтып жатып, өтүлгөн бардык чокулар түз тамырга илинет. Эки эвристика менен амортизацияланган татаалдык — Аккермандын тескери функциясы, иш жүзүндө константадан айырмаланбайт.
DSU кайда атат: кырлар кошулганда байланыш компоненттерин эсептөө, минималдуу каркас үчүн Краскалдын алгоритми (4-деңгээл), «бириктир жана сура» маселелери.
Тапшырма: DSU структурасына ар бир топтун өлчөмүн эсептөөнү кошуңуз (size массиви, бириктирүүдө size[a] += size[b]) жана «x тобунда канча элемент бар» суроосуна жооп бериңиз.
Сабакты өттүм деп белгилеңиз — 3-деңгээл аяктады, алдыда графтар!