Огтлолцолгүй олонлогийн нэгдэл¶
Энэ өгүүлэлд Огтлолцолгүй олонлогийн нэгдэл буюу DSU өгөгдлийн бүтцийг авч үзнэ. Хоёр үндсэн үйлдлээсээ болж үүнийг Union Find гэж бас олонтаа нэрлэдэг.
Энэ өгөгдлийн бүтэц дараах боломжуудыг өгнө. Бидэнд хэд хэдэн элемент өгөгдсөн ба тус бүр нь тусдаа олонлог юм. DSU нь дурын хоёр олонлогийг нэгтгэх үйлдэлтэй байх ба тодорхой элемент аль олонлогт байгааг хэлж чадна. Сонгодог хувилбар нь гурав дахь үйлдлийг мөн нэвтрүүлдэг: шинэ элементээс олонлог үүсгэж чадна.
Тиймээс энэ өгөгдлийн бүтцийн үндсэн интерфейс ердөө гурван үйлдлээс бүрдэнэ:
make_set(v)—vшинэ элементээс бүрдэх шинэ олонлог үүсгэнэunion_sets(a, b)— заасан хоёр олонлогийг (aэлемент байрлаж буй олонлог баbэлемент байрлаж буй олонлог) нэгтгэнэfind_set(v)—vэлементийг агуулсан олонлогийн төлөөлөгчийг (мөн удирдагч гэж нэрлэдэг) буцаана. Энэ төлөөлөгч нь өөрийн харгалзах олонлогийн элемент юм. Үүнийг өгөгдлийн бүтэц өөрөө олонлог бүрд сонгодог (мөн цаг хугацааны явцад, тухайлбалunion_setsдуудалтуудын дараа өөрчлөгдөж болно). Энэ төлөөлөгчийг ашиглан хоёр элемент нэг олонлогийн хэсэг мөн эсэхийг шалгаж болно. Хэрэвfind_set(a) == find_set(b)болaбаbяг нэг олонлогт байна. Эс бөгөөс тэдгээр өөр өөр олонлогт байна.
Дараа нь илүү дэлгэрэнгүй тайлбарласнаар энэ өгөгдлийн бүтэц нь эдгээр үйлдэл бүрийг дунджаар бараг $O(1)$ хугацаанд гүйцэтгэх боломж олгоно.
Мөн дэд хэсгүүдийн нэгэнд DSU-ийн өөр нэг бүтцийг тайлбарласан бөгөөд энэ нь $O(\log n)$ гэсэн илүү удаан дундаж complexity-д хүрдэг ч ердийн DSU бүтцээс илүү хүчирхэг байж болно.
Үр ашигтай өгөгдлийн бүтэц байгуулах¶
Бид олонлогуудыг мод хэлбэрээр хадгална: мод бүр нэг олонлогт харгалзана. Модны үндэс нь тухайн олонлогийн төлөөлөгч/удирдагч байх болно.
Дараах зурган дээр ийм модны дүрслэлийг харж болно.
Эхэндээ элемент бүр ганц олонлог болж эхлэх тул орой бүр өөрийн гэсэн мод байна. Дараа нь бид 1 элементийг агуулсан олонлог ба 2 элементийг агуулсан олонлогийг нэгтгэнэ. Дараа нь бид 3 элементийг агуулсан олонлог ба 4 элементийг агуулсан олонлогийг нэгтгэнэ. Сүүлийн алхамд бид 1 элементийг агуулсан олонлог ба 3 элементийг агуулсан олонлогийг нэгтгэнэ.
Хэрэгжүүлэлтийн хувьд энэ нь модон дахь шууд өвгийг заасан лавлагааг хадгалах parent массивыг арчлах шаардлагатай гэсэн үг юм.
Гэнэн хэрэгжүүлэлт¶
Бид Огтлолцолгүй олонлогийн нэгдэл өгөгдлийн бүтцийн эхний хэрэгжүүлэлтийг аль хэдийн бичиж чадна. Энэ нь эхэндээ нэлээд үр ашиггүй байх боловч дараа нь бид хоёр оновчлол ашиглан үүнийг сайжруулж, функцийн дуудалт бүр бараг тогтмол хугацаа авдаг болгож чадна.
Бидний хэлсэнчлэн элементүүдийн олонлогийн тухай бүх мэдээллийг parent массивд хадгална.
Шинэ олонлог үүсгэхийн тулд (make_set(v) үйлдэл) бид зүгээр л v оройд үндэстэй мод үүсгэнэ, өөрөөр хэлбэл тэр нь өөрийнхөө өвөг болно.
Хоёр олонлогийг нэгтгэхийн тулд (union_sets(a, b) үйлдэл) бид эхлээд a байрлаж буй олонлогийн төлөөлөгч ба b байрлаж буй олонлогийн төлөөлөгчийг олно.
Хэрэв төлөөлөгчид ижил бол бидэнд хийх зүйл байхгүй, олонлогууд аль хэдийн нэгтгэгдсэн байна.
Эс бөгөөс бид зүгээр л нэг төлөөлөгчийг нөгөө төлөөлөгчийн эцэг гэж зааж болно — ингэснээр хоёр модыг нэгтгэнэ.
Эцэст нь төлөөлөгч олох функцийн хэрэгжүүлэлт (find_set(v) үйлдэл):
бид v оройн өвгүүдээр үндэс хүртэл буюу өвгийг заасан лавлагаа нь өөр рүүгээ хөтөлдөг орой хүртэл зүгээр л авирна.
Энэ үйлдлийг рекурсивээр амархан хэрэгжүүлдэг.
void make_set(int v) {
parent[v] = v;
}
int find_set(int v) {
if (v == parent[v])
return v;
return find_set(parent[v]);
}
void union_sets(int a, int b) {
a = find_set(a);
b = find_set(b);
if (a != b)
parent[b] = a;
}
Гэвч энэ хэрэгжүүлэлт үр ашиггүй.
Модууд урт гинж болж degenerate болохоор жишээ зохиоход амархан.
Тэр тохиолдолд find_set(v) дуудалт бүр $O(n)$ хугацаа авч болно.
Энэ нь бидний хүсэж буй complexity-оос (бараг тогтмол хугацаа) хол байна. Тиймээс бид ажлыг мэдэгдэхүйц хурдасгах боломж олгох хоёр оновчлолыг авч үзнэ.
Замын шахалтын оновчлол¶
Энэ оновчлолыг find_set-г хурдасгах зорилгоор зохиосон.
Хэрэв бид ямар нэг v оройн хувьд find_set(v)-г дуудвал бид үнэндээ v ба жинхэнэ төлөөлөгч p хоёрын хоорондох замд зочилсон бүх оройн хувьд төлөөлөгч p-г олно.
Заль мэх нь зочилсон орой бүрийн эцгийг шууд p болгож тохируулснаар эдгээр бүх зангилааны замыг богиносгох явдал юм.
Энэ үйлдлийг дараах зурган дээр харж болно.
Зүүн талд мод байгаа ба баруун талд find_set(7)-г дуудсаны дараах шахагдсан мод байгаа бөгөөд энэ нь зочилсон 7, 5, 3, 2 зангилааны замыг богиносгосон.
find_set-ийн шинэ хэрэгжүүлэлт нь дараах байдалтай:
int find_set(int v) {
if (v == parent[v])
return v;
return parent[v] = find_set(parent[v]);
}
Энгийн хэрэгжүүлэлт нь зорьсон зүйлээ хийнэ: эхлээд олонлогийн төлөөлөгчийг (үндэс орой) олно, дараа нь стек буцаж дэлгэрэх явцад зочилсон зангилаанууд төлөөлөгчид шууд холбогдоно.
Үйлдлийн энэ энгийн өөрчлөлт нь аль хэдийн дуудалт тутамд дунджаар $O(\log n)$ time complexity-д хүрнэ (энд баталгаагүйгээр). Үүнийг бүр илүү хурдан болгох хоёр дахь өөрчлөлт бий.
Хэмжээ / зэргээр нэгтгэх¶
Энэ оновчлолд бид union_set үйлдлийг өөрчилнө.
Тодруулбал, аль мод нөгөөдөө холбогдохыг өөрчилнө.
Гэнэн хэрэгжүүлэлтэд хоёр дахь мод үргэлж эхнийхэд холбогддог байсан.
Практикт энэ нь $O(n)$ урттай гинж агуулсан мод үүсгэхэд хүргэж болно.
Энэ оновчлолоор бид аль мод холбогдохыг маш болгоомжтой сонгож үүнээс зайлсхийнэ.
Ашиглаж болох олон эвристик бий. Хамгийн түгээмэл нь дараах хоёр арга юм: Эхний аргад бид модны хэмжээг зэрэг болгон ашиглах ба хоёр дахьд нь модны гүнийг (тодруулбал модны гүний дээд хязгаарыг, учир нь замын шахалт хэрэглэх үед гүн багасна) ашиглана.
Хоёр аргад оновчлолын мөн чанар ижил: бид бага зэрэгтэй модыг илүү их зэрэгтэй модонд холбоно.
Хэмжээгээр нэгтгэх хэрэгжүүлэлт энд байна:
void make_set(int v) {
parent[v] = v;
size[v] = 1;
}
void union_sets(int a, int b) {
a = find_set(a);
b = find_set(b);
if (a != b) {
if (size[a] < size[b])
swap(a, b);
parent[b] = a;
size[a] += size[b];
}
}
Модны гүн дээр суурилсан зэргээр нэгтгэх хэрэгжүүлэлт энд байна:
void make_set(int v) {
parent[v] = v;
rank[v] = 0;
}
void union_sets(int a, int b) {
a = find_set(a);
b = find_set(b);
if (a != b) {
if (rank[a] < rank[b])
swap(a, b);
parent[b] = a;
if (rank[a] == rank[b])
rank[a]++;
}
}
Time complexity¶
Өмнө дурдсанчлан хэрэв бид хоёр оновчлолыг — замын шахалт ба хэмжээ / зэргээр нэгтгэхийг — хослуулбал бид бараг тогтмол хугацааны асуулгад хүрнэ. Эцсийн хорогдуулсан time complexity нь $O(\alpha(n))$ болох нь тогтоогддог, энд $\alpha(n)$ нь маш удаан өсдөг Аккерманы урвуу функц юм. Үнэндээ энэ нь маш удаан өсдөг тул бүх боломжит $n$-ийн хувьд (ойролцоогоор $n < 10^{600}$) $4$-өөс хэтрэхгүй.
Хорогдуулсан complexity гэдэг нь олон үйлдлийн дараалал дээр үнэлэгдсэн, үйлдэл тутмын нийт хугацаа юм. Санаа нь ганц үйлдэл хорогдуулсан хугацаанаас хамаагүй удаан байхыг зөвшөөрөхийн зэрэгцээ бүхэл дарааллын нийт хугацааг баталгаажуулах явдал юм. Жишээ нь бидний тохиолдолд ганц дуудалт хамгийн муу тохиолдолд $O(\log n)$ авч болох ч хэрэв бид ийм $m$ дуудалтыг дараалуулан хийвэл эцэст нь $O(\alpha(n))$ дундаж хугацаатай болно.
Энэ time complexity-ийн баталгааг мөн бид үзүүлэхгүй, учир нь энэ нь нэлээд урт бөгөөд төвөгтэй.
Мөн хэмжээ / зэргээр нэгтгэдэг боловч замын шахалтгүй DSU нь асуулга тутамд $O(\log n)$ хугацаанд ажилладгийг дурдах нь зүйтэй.
Индексээр холбох / зоос шидэлтээр холбох¶
Зэргээр нэгтгэх ба хэмжээгээр нэгтгэх хоёулаа олонлог бүрд нэмэлт өгөгдөл хадгалж, нэгтгэх үйлдэл бүрийн явцад эдгээр утгыг арчлахыг шаарддаг. Нэгтгэх үйлдлийг бага зэрэг хялбарчлах санамсаргүй алгоритм мөн байдаг: индексээр холбох.
Бид олонлог бүрд индекс гэж нэрлэгдэх санамсаргүй утга оноож, бага индекстэй олонлогийг их индекстэйд холбоно. Илүү том олонлог нь бага олонлогоос илүү том индекстэй байх магадлалтай тул энэ үйлдэл хэмжээгээр нэгтгэхтэй нягт холбоотой. Үнэндээ энэ үйлдэл хэмжээгээр нэгтгэхтэй ижил time complexity-тэй болохыг баталж болно. Гэвч практикт энэ нь хэмжээгээр нэгтгэхээс бага зэрэг удаан.
Complexity-ийн баталгаа ба бүр илүү олон нэгтгэх аргыг эндээс олж болно.
void make_set(int v) {
parent[v] = v;
index[v] = rand();
}
void union_sets(int a, int b) {
a = find_set(a);
b = find_set(b);
if (a != b) {
if (index[a] < index[b])
swap(a, b);
parent[b] = a;
}
}
Аль олонлогийг нөгөөд холбохыг шийдэхийн тулд зүгээр л зоос шидэх нь ижил complexity-тэй гэсэн нийтлэг буруу ойлголт бий. Гэвч энэ нь үнэн биш. Дээр холбосон өгүүлэлд зоос шидэлтээр холбохыг замын шахалттай хослуулбал $\Omega\left(n \frac{\log n}{\log \log n}\right)$ complexity-тэй болно гэсэн таамаг дэвшүүлсэн. Мөн бенчмаркуудад энэ нь хэмжээ/зэргээр нэгтгэх буюу индексээр холбохоос хамаагүй муу ажилладаг.
void union_sets(int a, int b) {
a = find_set(a);
b = find_set(b);
if (a != b) {
if (rand() % 2)
swap(a, b);
parent[b] = a;
}
}
Хэрэглээ ба төрөл бүрийн сайжруулалт¶
Энэ хэсэгт бид энэ өгөгдлийн бүтцийн хэд хэдэн хэрэглээг, тривиаль хэрэглээ ба өгөгдлийн бүтцийн зарим сайжруулалт хоёуланг нь авч үзнэ.
Граф дахь холбоост компонентууд¶
Энэ бол DSU-ийн илэрхий хэрэглээнүүдийн нэг юм.
Албан ёсоор бодлогыг дараах байдлаар тодорхойлно: Эхэндээ бидэнд хоосон граф байна. Бид орой ба чиглэлгүй ирмэг нэмэх ёстой бөгөөд $(a, b)$ хэлбэрийн буюу "$a$ ба $b$ оройнууд графын нэг холбоост компонентод байгаа юу?" гэсэн асуулгад хариулах ёстой.
Энд бид өгөгдлийн бүтцийг шууд хэрэглэж, орой эсвэл ирмэг нэмэх ба асуулгыг дунджаар бараг тогтмол хугацаанд боловсруулдаг шийдэл авч болно.
Энэ хэрэглээ нэлээд чухал, учир нь бараг ижил бодлого хамгийн бага тэлэх мод олох Крускалын алгоритм-д гарч ирдэг. DSU ашиглан бид $O(m \log n + n^2)$ complexity-г $O(m \log n)$ болгож сайжруулж чадна.
Зураг дахь холбоост компонентуудыг хайх¶
DSU-ийн хэрэглээнүүдийн нэг нь дараах бодлого юм: $n \times m$ пикселийн зураг байна. Анх бүгд цагаан байсан боловч дараа нь хэдэн хар пиксел зурагдсан. Та эцсийн зураг дахь цагаан холбоост компонент бүрийн хэмжээг тодорхойлохыг хүсэж байна.
Шийдлийн хувьд бид зураг дахь бүх цагаан пикселийг гүйж, нүд бүрийн хувьд түүний дөрвөн хөршийг гүйж, хэрэв хөрш нь цагаан бол union_sets-г дуудна.
Ингэснээр бид зургийн пикселүүдэд харгалзах $n m$ зангилаатай DSU-тэй болно.
DSU дахь үүссэн модууд нь хүссэн холбоост компонентууд юм.
Бодлогыг мөн DFS эсвэл BFS-ээр бодож болох боловч энд тайлбарласан арга нь давуу талтай: энэ нь матрицыг мөр мөрөөр нь (өөрөөр хэлбэл мөрийг боловсруулахад бидэнд зөвхөн өмнөх ба одоогийн мөр хэрэгтэй ба зөвхөн нэг мөрийн элементүүдэд зориулж байгуулсан DSU хэрэгтэй) $O(\min(n, m))$ санах ойд боловсруулж чадна.
Олонлог бүрд нэмэлт мэдээлэл хадгалах¶
DSU нь олонлогуудад нэмэлт мэдээлэл амархан хадгалах боломж олгоно.
Энгийн жишээ бол олонлогийн хэмжээ юм: хэмжээг хадгалахыг Хэмжээгээр нэгтгэх хэсэгт аль хэдийн тайлбарласан (мэдээллийг олонлогийн одоогийн төлөөлөгч хадгалж байсан).
Үүнтэй ижил аргаар — төлөөлөгч зангилаанууд дээр хадгалснаар — та олонлогуудын тухай өөр ямар ч мэдээллийг хадгалж болно.
Хэрчим дагуух үсрэлтийг шахах / Дэд массивыг офлайнаар будах¶
DSU-ийн нэг түгээмэл хэрэглээ нь дараах юм: Оройнуудын олонлог байгаа ба орой бүр өөр орой руу гарах ирмэгтэй. DSU-тэй бол өгөгдсөн эхлэх цэгээс бүх ирмэгийг дагаж явсны дараа хүрэх төгсгөлийн цэгийг бараг тогтмол хугацаанд олж чадна.
Энэ хэрэглээний сайн жишээ бол дэд массивыг будах бодлого юм. Бидэнд $L$ урттай хэрчим байгаа ба элемент бүр анх 0 өнгөтэй. Бид асуулга $(l, r, c)$ бүрийн хувьд $[l, r]$ дэд массивыг $c$ өнгөөр дахин будах ёстой. Эцэст нь бид нүд бүрийн эцсийн өнгийг олохыг хүсэж байна. Бид бүх асуулгыг урьдчилан мэддэг гэж үзнэ, өөрөөр хэлбэл бодлого офлайн юм.
Шийдлийн хувьд бид нүд бүрд дараагийн будаагүй нүд рүү заасан холбоос хадгалдаг DSU хийж болно. Ингэснээр анх нүд бүр өөр рүүгээ заана. Хэрчмийг дахин будах хүсэлтийн нэгийг гүйцэтгэсний дараа тэр хэрчмийн бүх нүд хэрчмийн дараах нүд рүү заана.
Одоо энэ бодлогыг бодохын тулд бид асуулгуудыг урвуу дарааллаар авч үзнэ: сүүлийнхээс эхнийх хүртэл. Ингэснээр бид асуулга гүйцэтгэх үед $[l, r]$ дэд массив дахь яг будаагүй нүднүүдийг л будах хэрэгтэй болно. Бусад бүх нүд эцсийн өнгөө аль хэдийн агуулж байна. Бүх будаагүй нүдийг хурдан гүйхийн тулд бид DSU ашиглана. Бид хэрчмийн доторх хамгийн зүүн будаагүй нүдийг олж, түүнийг дахин будаад, заагчаар баруун тийш дараагийн хоосон нүд рүү шилжинэ.
Энд бид замын шахалттай DSU ашиглаж болох ч зэрэг / хэмжээгээр нэгтгэхийг ашиглаж болохгүй (учир нь нэгтгэсний дараа хэн удирдагч болох нь чухал). Тиймээс complexity нь нэгтгэлт тутамд $O(\log n)$ болно (энэ нь бас нэлээд хурдан).
Хэрэгжүүлэлт:
for (int i = 0; i <= L; i++) {
make_set(i);
}
for (int i = m-1; i >= 0; i--) {
int l = query[i].l;
int r = query[i].r;
int c = query[i].c;
for (int v = find_set(l); v <= r; v = find_set(v)) {
answer[v] = c;
parent[v] = v + 1;
}
}
Нэг оновчлол бий:
Хэрэв бид дараагийн будаагүй нүдийг нэмэлт end[] массивд хадгалбал зэрэг / хэмжээгээр нэгтгэхийг ашиглаж болно.
Тэгвэл бид хоёр олонлогийг эвристикийнх нь дагуу нэг болгон нэгтгэж, $O(\alpha(n))$ шийдэл авна.
Төлөөлөгч хүртэлх зайг дэмжих¶
Заримдаа DSU-ийн тодорхой хэрэглээнүүдэд орой ба түүний олонлогийн төлөөлөгчийн хоорондох зайг (өөрөөр хэлбэл модон дахь одоогийн зангилаанаас модны үндэс хүртэлх замын уртыг) арчлах шаардлагатай болдог.
Хэрэв бид замын шахалт ашиглахгүй бол зай нь зүгээр л рекурсив дуудалтын тоо байна. Гэвч энэ нь үр ашиггүй байх болно.
Гэсэн хэдий ч хэрэв бид зангилаа бүрд нэмэлт мэдээлэл болгон эцэг хүртэлх зайг хадгалбал замын шахалт хийх боломжтой.
Хэрэгжүүлэлтэд parent[]-ийн хувьд хосуудын массив ашиглах нь тохиромжтой ба find_set функц одоо хоёр тоо буцаана: олонлогийн төлөөлөгч ба түүн хүртэлх зай.
void make_set(int v) {
parent[v] = make_pair(v, 0);
rank[v] = 0;
}
pair<int, int> find_set(int v) {
if (v != parent[v].first) {
int len = parent[v].second;
parent[v] = find_set(parent[v].first);
parent[v].second += len;
}
return parent[v];
}
void union_sets(int a, int b) {
a = find_set(a).first;
b = find_set(b).first;
if (a != b) {
if (rank[a] < rank[b])
swap(a, b);
parent[b] = make_pair(a, 1);
if (rank[a] == rank[b])
rank[a]++;
}
}
Замын уртын тэгш сондгой байдлыг дэмжих / Хоёр хэсэгт байдлыг онлайнаар шалгах¶
Удирдагч хүртэлх замын уртыг тооцоолохтой ижил аргаар түүний өмнөх замын уртын тэгш сондгой байдлыг арчлах боломжтой. Яагаад энэ хэрэглээ тусдаа догол мөрөнд байна вэ?
Замын тэгш сондгой байдлыг хадгалах ер бусын шаардлага дараах бодлогод гарч ирдэг: анх бидэнд хоосон граф өгөгдсөн, түүнд ирмэг нэмж болох ба бид "энэ оройг агуулсан холбоост компонент хоёр хэсэгт мөн үү?" гэсэн хэлбэрийн асуулгад хариулах ёстой.
Энэ бодлогыг бодохын тулд бид компонентуудыг хадгалах DSU хийж, орой бүрийн хувьд төлөөлөгч хүртэлх замын тэгш сондгой байдлыг хадгална. Ингэснээр бид ирмэг нэмэх нь хоёр хэсэгт байдлыг зөрчихөд хүргэж байгаа эсэхийг хурдан шалгаж чадна: тухайлбал хэрэв ирмэгийн төгсгөлүүд нэг холбоост компонентод байх ба удирдагч хүртэл ижил тэгш сондгой байдалтай урттай бол энэ ирмэгийг нэмэх нь сондгой урттай цикл үүсгэх ба компонент хоёр хэсэгт байх шинж чанараа алдана.
Бидний тулгарах цорын ганц бэрхшээл бол union_find аргад тэгш сондгой байдлыг тооцоолох явдал юм.
Хэрэв бид хоёр холбоост компонентыг нэг болгон холбох $(a, b)$ ирмэг нэмбэл нэг модыг нөгөөд холбох үед бид тэгш сондгой байдлыг тохируулах хэрэгтэй.
Өөр олонлогт холбогдох олонлогийн удирдагчид олгох тэгш сондгой байдлыг тооцоолох томьёог гаргая. $x$ нь $a$ оройноос түүний удирдагч $A$ хүртэлх замын уртын тэгш сондгой байдал, $y$ нь $b$ оройноос түүний удирдагч $B$ хүртэлх замын уртын тэгш сондгой байдал, $t$ нь нэгтгэсний дараа $B$-д оноох ёстой хүссэн тэгш сондгой байдал байг. Зам нь гурван хэсгээс бүрдэнэ: $B$-ээс $b$ хүртэл, $b$-ээс $a$ хүртэл (энэ нь нэг ирмэгээр холбогдсон тул тэгш сондгой байдал нь $1$), ба $a$-аас $A$ хүртэл. Тиймээс бид дараах томьёог авна ($\oplus$ нь XOR үйлдлийг тэмдэглэнэ):
Ингэснээр бид хэдэн ч нэгтгэлт хийсэн ирмэгүүдийн тэгш сондгой байдал нэг удирдагчаас нөгөөд дамжина.
Бид тэгш сондгой байдлыг дэмждэг DSU-ийн хэрэгжүүлэлтийг өгье. Өмнөх хэсгийн адил бид өвөг ба тэгш сондгой байдлыг хадгалахад хос ашиглана. Түүнчлэн олонлог бүрийн хувьд бид bipartite[] массивд түүнийг хоёр хэсэгт хэвээр байгаа эсэхийг хадгална.
void make_set(int v) {
parent[v] = make_pair(v, 0);
rank[v] = 0;
bipartite[v] = true;
}
pair<int, int> find_set(int v) {
if (v != parent[v].first) {
int parity = parent[v].second;
parent[v] = find_set(parent[v].first);
parent[v].second ^= parity;
}
return parent[v];
}
void add_edge(int a, int b) {
pair<int, int> pa = find_set(a);
a = pa.first;
int x = pa.second;
pair<int, int> pb = find_set(b);
b = pb.first;
int y = pb.second;
if (a == b) {
if (x == y)
bipartite[a] = false;
} else {
if (rank[a] < rank[b])
swap (a, b);
parent[b] = make_pair(a, x^y^1);
bipartite[a] &= bipartite[b];
if (rank[a] == rank[b])
++rank[a];
}
}
bool is_bipartite(int v) {
return bipartite[find_set(v).first];
}
Офлайн RMQ (интервал дахь хамгийн бага элемент) дунджаар $O(\alpha(n))$-д / Арпагийн заль мэх¶
Бидэнд a[] массив өгөгдсөн ба бид массивын өгөгдсөн хэрчмүүд дэх зарим минимумыг тооцоолох ёстой.
Энэ бодлогыг DSU-ээр бодох санаа нь дараах юм:
Бид массивыг гүйж, i дахь элемент дээр байхдаа R == i байх бүх (L, R) асуулгад хариулна.
Үүнийг үр ашигтай хийхийн тулд бид эхний i элементийг ашиглан дараах бүтэцтэй DSU хадгална: элементийн эцэг нь түүний баруун талд байгаа дараагийн бага элемент байна.
Тэгвэл энэ бүтцийг ашиглан асуулгын хариу нь a[find_set(L)] буюу L-ийн баруун талд байгаа хамгийн бага тоо болно.
Энэ арга нь мэдээж зөвхөн офлайнаар ажиллана, өөрөөр хэлбэл бид бүх асуулгыг урьдчилан мэддэг бол.
Бид замын шахалт хэрэглэж болохыг харахад амархан. Мөн хэрэв бид жинхэнэ удирдагчийг тусдаа массивд хадгалбал зэргээр нэгтгэхийг ч ашиглаж болно.
struct Query {
int L, R, idx;
};
vector<int> answer;
vector<vector<Query>> container;
container[i] нь R == i байх бүх асуулгыг агуулна.
stack<int> s;
for (int i = 0; i < n; i++) {
while (!s.empty() && a[s.top()] > a[i]) {
parent[s.top()] = i;
s.pop();
}
s.push(i);
for (Query q : container[i]) {
answer[q.idx] = a[find_set(q.L)];
}
}
Өнөө үед энэ алгоритмыг Арпагийн заль мэх гэж нэрлэдэг. Үүнийг бие даан нээж, түгээмэл болгосон AmirReza Poorakhavan-ы нэрээр нэрлэсэн. Хэдийгээр энэ алгоритм түүний нээлтээс өмнө ч байсан.
Офлайн LCA (модон дахь хамгийн бага нийтлэг өвөг) дунджаар $O(\alpha(n))$-д¶
LCA олох алгоритмыг Хамгийн бага нийтлэг өвөг - Таржаны офлайн алгоритм өгүүлэлд авч үзсэн. Энэ алгоритм нь энгийн байдлаараа LCA олох бусад алгоритмуудтай харьцуулахад давуу талтай (ялангуяа Фарах-Колтон, Бендер-ийнх шиг оновчтой алгоритмтай харьцуулбал).
DSU-г олонлогийн жагсаалтад ил хадгалах / Төрөл бүрийн өгөгдлийн бүтцийг нэгтгэх үед энэ санааны хэрэглээ¶
DSU-г хадгалах өөр нэг арга бол олонлог бүрийг түүний элементүүдийн ил хадгалагдсан жагсаалт хэлбэрээр хадгалах явдал юм. Үүний зэрэгцээ элемент бүр мөн өөрийн олонлогийн төлөөлөгч рүү заасан лавлагаа хадгална.
Эхлээд харахад энэ нь үр ашиггүй өгөгдлийн бүтэц мэт харагдана: хоёр олонлогийг нэгтгэхдээ бид нэг жагсаалтыг нөгөөгийнх нь төгсгөлд нэмж, жагсаалтуудын нэгийн бүх элементэд удирдагчийг шинэчлэх шаардлагатай болно.
Гэвч жинлэх эвристик (Хэмжээгээр нэгтгэхтэй төстэй) ашиглах нь асимптот complexity-г мэдэгдэхүйц бууруулж чадах нь тогтоогддог: $n$ элемент дээр $m$ асуулга гүйцэтгэхэд $O(m + n \log n)$.
Жинлэх эвристик гэж бид хоёр олонлогийн багыг нь илүү том олонлогт үргэлж нэмнэ гэсэн утгыг ойлгоно.
Нэг олонлогийг нөгөөд нэмэхийг union_sets-д хэрэгжүүлэхэд амархан бөгөөд нэмэгдэж буй олонлогийн хэмжээтэй пропорциональ хугацаа авна.
Мөн find_set-д удирдагчийг хайх нь хадгалах энэ аргаар $O(1)$ хугацаа авна.
$m$ асуулга гүйцэтгэх time complexity $O(m + n \log n)$ болохыг баталъя.
Бид дурын $x$ элементийг тогтоож, union_sets нэгтгэх үйлдэлд түүнд хэдэн удаа хүрснийг тоолно.
$x$ элементэд анх удаа хүрэх үед шинэ олонлогийн хэмжээ дор хаяж $2$ байна.
Хоёр дахь удаа хүрэх үед үүссэн олонлог дор хаяж $4$ хэмжээтэй байна, учир нь бага олонлог нь их олонлогт нэмэгддэг.
Гэх мэтчилэн.
Энэ нь $x$-г хамгийн ихдээ $\log n$ нэгтгэх үйлдэлд л шилжүүлж болно гэсэн үг юм.
Тиймээс бүх оройн нийлбэр нь $O(n \log n)$ дээр хүсэлт бүрд $O(1)$ нэмснийг өгнө.
Хэрэгжүүлэлт энд байна:
vector<int> lst[MAXN];
int parent[MAXN];
void make_set(int v) {
lst[v] = vector<int>(1, v);
parent[v] = v;
}
int find_set(int v) {
return parent[v];
}
void union_sets(int a, int b) {
a = find_set(a);
b = find_set(b);
if (a != b) {
if (lst[a].size() < lst[b].size())
swap(a, b);
while (!lst[b].empty()) {
int v = lst[b].back();
lst[b].pop_back();
parent[v] = a;
lst[a].push_back (v);
}
}
}
Бага хэсгийг том хэсэгт нэмэх энэ санааг DSU-тэй огт хамааралгүй олон шийдэлд ч ашиглаж болно.
Жишээ нь дараах бодлогыг авч үзье: бидэнд мод өгөгдсөн, навч бүрд тоо оноогдсон (ижил тоо өөр өөр навчид олон удаа гарч болно). Бид модны зангилаа бүрийн хувьд түүний дэд мод дахь ялгаатай тоонуудын тоог тооцоолохыг хүсэж байна.
Энэ бодлогод ижил санааг хэрэглэснээр дараах шийдлийг авах боломжтой: бид DFS хэрэгжүүлж болох ба энэ нь бүхэл тоонуудын олонлог руу заасан заагчийг буюу тэр дэд мод дахь тоонуудын жагсаалтыг буцаана. Дараа нь одоогийн зангилааны хариуг авахын тулд (хэрэв тэр нь мэдээж навч биш бол) бид тэр зангилааны бүх хүүхдийн хувьд DFS дуудаж, хүлээн авсан бүх олонлогийг нэгтгэнэ. Үүссэн олонлогийн хэмжээ нь одоогийн зангилааны хариу байх болно. Олон олонлогийг үр ашигтай нэгтгэхийн тулд бид дээр тайлбарласан жороо хэрэглэнэ: бид олонлогуудыг багыг нь томд зүгээр л нэмэх замаар нэгтгэнэ. Эцэст нь бид $O(n \log^2 n)$ шийдэл авна, учир нь нэг тоо олонлогт хамгийн ихдээ $O(\log n)$ удаа л нэмэгдэнэ.
DSU-г тодорхой модны бүтэц арчлах замаар хадгалах / Гүүрийг онлайнаар дунджаар $O(\alpha(n))$-д олох¶
DSU-ийн хамгийн хүчирхэг хэрэглээнүүдийн нэг нь шахагдсан ба шахагдаагүй мод хоёуланг нь хадгалах боломж олгодог явдал юм. Шахагдсан хэлбэрийг модуудыг нэгтгэх ба хоёр орой нэг модонд байгаа эсэхийг шалгахад ашиглаж болох ба шахагдаагүй хэлбэрийг — жишээ нь — өгөгдсөн хоёр оройн хоорондох замыг хайх буюу модны бүтцийн бусад тойролтод ашиглаж болно.
Хэрэгжүүлэлтийн хувьд энэ нь шахагдсан өвгүүдийн parent[] массиваас гадна бид шахагдаагүй өвгүүдийн real_parent[] массивыг хадгалах шаардлагатай гэсэн үг юм.
Энэ нэмэлт массивыг арчлах нь complexity-г мууруулахгүй нь тривиаль:
түүн дэх өөрчлөлт зөвхөн бид хоёр модыг нэгтгэх үед, зөвхөн нэг элементэд гарна.
Нөгөө талаас практикт хэрэглэхэд бид ихэвчлэн хоёр үндэс зангилааг ашиглахаас өөр, заасан ирмэг ашиглан модуудыг холбох шаардлагатай болдог. Энэ нь бидэнд модуудын нэгийг дахин үндэслэхээс (ирмэгийн төгсгөлүүдийг модны шинэ үндэс болгохоос) өөр сонголт байхгүй гэсэн үг юм.
Эхлээд харахад энэ дахин үндэслэх нь маш өртөгтэй бөгөөд time complexity-г ихээхэн мууруулах мэт санагдана.
Үнэхээр модыг $v$ оройд үндэслэхийн тулд бид оройноос хуучин үндэс хүртэл явж, тэр зам дээрх бүх зангилааны parent[] ба real_parent[] дэх чиглэлийг өөрчлөх ёстой.
Гэвч бодит байдал дээр тийм ч муу биш, бид өмнөх хэсгүүдийн санаатай төстэйгээр хоёр модны багыг нь дахин үндэслээд дунджаар $O(\log n)$ авч болно.
Дэлгэрэнгүйг (time complexity-ийн баталгаа орно) Гүүрийг онлайнаар олох өгүүллээс олж болно.
Түүхэн эргэн харалт¶
DSU өгөгдлийн бүтэц удаан хугацааны турш мэдэгдэж байсан.
Энэ бүтцийг модны ой хэлбэрээр хадгалах энэ аргыг 1964 онд Galler, Fisher нар анх тайлбарласан бололтой (Galler, Fisher, "An Improved Equivalence Algorithm"), гэхдээ time complexity-ийн бүрэн шинжилгээг хамаагүй хожуу хийсэн.
Замын шахалт ба Зэргээр нэгтгэх оновчлолуудыг McIlroy, Morris нар, мөн тэднээс үл хамааран Tritter боловсруулсан.
Hopcroft, Ullman нар 1973 онд $O(\log^\star n)$ time complexity-г үзүүлсэн (Hopcroft, Ullman "Set-merging algorithms") — энд $\log^\star$ нь давтсан логарифм юм (энэ нь удаан өсдөг функц боловч Аккерманы урвуу функц шиг удаан биш).
$O(\alpha(n))$ үнэлгээг анх удаа 1975 онд үзүүлсэн (Tarjan "Efficiency of a Good But Not Linear Set Union Algorithm"). Хожим нь 1985 онд тэрээр Leeuwen-тэй хамтран хэд хэдэн өөр зэргийн эвристик ба замыг шахах аргуудын хувьд олон complexity-ийн шинжилгээ нийтэлсэн (Tarjan, Leeuwen "Worst-case Analysis of Set Union Algorithms").
Эцэст нь 1989 онд Fredman, Sachs нар хүлээн зөвшөөрөгдсөн тооцооллын загварт огтлолцолгүй олонлогийн нэгдлийн бодлогын аль ч алгоритм дунджаар дор хаяж $O(\alpha(n))$ хугацаанд ажиллах ёстойг баталсан (Fredman, Saks, "The cell probe complexity of dynamic data structures").