Disjoint Set Union (Union Find)-н тухай.
Бидэнд анх аль ч хоёр орой нь хоорондоо холбогдоогүй граф байгаа гэж үзье. Өөрөөр хэлбэл нийт N ширхэг компонент байгаа. Нийт Q ширхэг холболт байгаа ба x, y гэсэн хоёр оройг холбох ба энэ бүх холболтын дараа нийт хэдэн ширхэг компонент байгааг олох жишээ бодлого бодоцгооё. par[N], s[N] гэсэн array авж үзье. par[x] нь x оройн эцгийг, s[x] нь энэ оройд хэдэн хүү байгааг хадгална. Анх бүх i-н хувьд par[i] = i, s[i] = 1 байна. Эхлээд find(x) гэсэн функц тодорхойлъё. Энэ нь x гэсэн оройн хамгийн дээд эцэг буюу root оройг буцаана. par[r] == r тохиолдолд энэхүү r орой нь root. Учир нь r оройн эцэг нь өөрөө тул үүнээс дээш орой үгүй. Одоо буцаад x, y хоёр оройг холбох асуудалдаа орцгооё. Холбохын тулд эхлээд бид rootX = find(x), rootY = find(y) гэж олбол x, y гэсэн хоёр оройн тус тусын хамгийн дээд эцгийг олж чадсан гэсэн үг. Хэрвээ энэ хоёр орой нь ижилхэн бол x, y хоёр орой нь аль хэдийн нэг компонентэд байгаа нь тодорхой. Энэ тохиолдолд бид өөр зүйл хийх шаардлагагүй. Учир нь компонент хасагдахгүй. Хэрвээ энэ хоёр орой нь өөр бол тусдаа компонентэд байгаа ба энэ хоёр компонентийг нэгтгэж нэг болгох ёстой. Энэ үед нийт компонентийн тоо нэгээр багасна. Харин холбохын тулд аль бага хүүтэй root оройг сонгоно.(rootY-н хүүгийн тоо нь rootX-с бага гэж үзье) par[rootY] = rootX, s[rootX] += s[rootY] болно. Энэ нь rootY гэсэн орой нь rootX-г заадаг болох ба үүний дараа rootY-д харьяалагддаг байсан бүх оройнуудын дээд root нь rootX болох тул rootX-н хүүнүүд нь rootY-д байсан хүүнүүдээр нэмэгдэнэ. Энэ нь салангид байсан хоёр компонент нэгдэж чадсан гэсэн үг билээ. Бидний хамгийн гол анзаарах зүйл нь find(x) функц юм. par[x] = find( par[x]) ба энэ нь x оройг x оройн дээд эцэгтэй шууд холбож байгаа юм. Учир нь x оройн дээд эцгийг дахиж олох байсан гэж үзвэл x оройн эцэг нь энэ компонентийн дээд эцэг тул маш хурдан олж чадна. Доорх код энэд байгаа.
- // union find
- #include <bits/stdc++.h>
- using namespace std;
- const int N = 200000; // тогтмол хувьсагч
- int n; // оройн тоо
- int q; // хүсэлтийн тоо
- int s[N]; // s[x] нь x гэсэн дээд эцэгтэй компонентийн хэмжээ
- int comp; // нийт компонентийн тоо
- int par[N]; // par[x] нь x оройн эцгийг хадгална.
- int find(int x) { // x оройн дээд эцгийг олох функц
- if(x == par[x]) { // x оройн эцэг өөрөө гэдэг нь хамгийн дээд орой мөн
- return x; // тиймээс x оройг буцаана.
- }
- // эсрэг тохиолдолд
- // par[x] оройн дээд эцэг нь x оройн дээд эцэг тул par[x] оройн
- // дээд эцгийг олно.
- int root = find( par[x] );
- // root нь дээд эцэг бөгөөд
- // x оройн эцгийг root гэж оноосноор холболтын урт багасна.
- // ингэснээр бидэнд ашигтай.
- par[x] = root;
- return root;
- }
- int main() {
- cin >> n; // оройн тоо
- comp = n; // n ширхэг компонент байгаа.
- for(int i = 1; i <= n; i++) {
- par[i] = i; // i оройн эцэг нь өөрөө
- s[i] = 1; // хэмжээ нь 1
- }
- cin >> q; // хүсэлтийн тоо
- while(q--) {
- int x, y; // холбох 2 орой
- cin >> x >> y;
- int rootX = find(x); // x оройн дээд эцгийг олно.
- int rootY = find(y); // y оройн дээд эцгийг олно.
- if(rootX == rootY) { // анхны 2 оройн дээд эцэг нь ижил гэдэг нь
- // нэг компонентэд энэ 2 орой оршиж байна.
- // тиймээс юу ч хийх шаардлагагүй.
- } else { // эсрэг тохиолдолд нэгтгэх ёстой.
- // 2 компонент нэгдэж байгаа тул нийт компонентийн тоо нэгээр хасагдана.
- comp--;
- if(s[rootX] > s[rootY]) { // хэмжээ ихэд нь хэмжээ багатай
- // компонентийг холбоно.
- par[rootY] = rootX; // rootY-н эцгийг rootX болгоно.
- s[rootX] += s[rootY]; // rootX эцэгтэй компонентийн хэмжээ нь нэмэгдэнэ.
- s[rootY] = 0;
- } else {
- par[rootX] = rootY; // rootX-н эцгийг rootY болгоно.
- s[rootY] += s[rootX]; // rootY эцэгтэй компонентийн хэмжээ нь нэмэгдэнэ.
- s[rootX] = 0;
- }
- }
- cout << comp << endl;
- }
- return 0;
- }
Comments
Post a Comment