Системаи маҷмӯаҳои ғайрибуришкунанда

Системаи маҷмӯаҳои ғайрибуришкунанда

Муқаддима

DSU (Disjoint Set Union) имкониятҳои зеринро фароҳам меорад: ба мо чандин элемент дода мешавад, ки ҳар кадоми онҳо дар оғоз маҷмӯи ҷудогона мебошанд. DSU амалиёти муттаҳид кардани ҳар ду маҷмӯаро дастгирӣ мекунад ва имкон медиҳад муайян кунем, ки элементи мушаххас дар кадом маҷмӯа ҷойгир аст. Дар варианти классикӣ амалиёти сеюм ҳам ворид мешавад — сохтани маҷмӯа аз элементи нав.

Ҳамин тавр, интерфейси DSU аз се функсия иборат аст:

• make_set(x) — маҷмӯаи навро аз як элементи $x$ месозад.
• find_set(x) — маҷмӯаеро меёбад, ки дар он элементи $x$ ҷойгир аст (одатан роҳбари маҷмӯаро бармегардонад).
• union_sets(x, y) — маҷмӯаҳоро, ки элементҳои $x$ ва $y$-ро дар бар мегиранд, муттаҳид мекунад.

Татбиқ

Ҳар як маҷмӯаро дар шакли дарахти решадор муаррифӣ мекунем. Қуллаҳо — ин элементҳои маҷмӯа мебошанд. Решаи дарахтро роҳбари маҷмӯа меноманд. Он гоҳ ҷангал аз дарахтон ҳосил мешавад, ки ҳар як дарахт ба як маҷмӯа мувофиқ аст.

Ду қулла дар як маҷмӯа ҳастанд танҳо ва танҳо вақте ки роҳбарони дарахтони онҳо якхелаанд.

Ҳалли соддалавҳона

Массиви parent месозем, ки дар он parent[x] — аҷдоди қуллаи аст (ва барои реша).