Edge-үүдийг жингээр нь sort хийгээд, cycle үүсгэхгүй хамгийн хямдыг нь сонгосоор бүх node-ыг холбоно.

Advanced & LegendХугацаа: O(m log m)Санах ой: O(n + m)
HackerRank дээр бодох

Эхлээд жижиг бодлого

4 node байна. Edge-үүд: 1–2 (1), 2–3 (2), 1–3 (3), 3–4 (4), 2–4 (5). Бүх node-ыг холбох, нийт жин нь хамгийн бага edge-үүдийг сонгоё.

Хямдаас нь авъя: 1–2 (1), 2–3 (2). 1–3 (3)-ыг авбал 1, 2, 3 тойрог болох тул алгасна. 3–4 (4)-ийг авна. Хариу 1 + 2 + 4 = 7.

Энгийн аргаас санаа руу

Энгийн арга бол n − 1 edge-ийн бүх хослолыг шалгах. Edge олон бол хослолын тоо асар их.

Гол санаа нь Greedy: edge-үүдийг жингээр нь sort хийгээд хамгийн хямдаас эхэлнэ. Edge хоёр өөр бүлгийг холбож байвал авна, нэг бүлгийн дотор байвал cycle үүсгэх тул алгасна. Хоёр node нэг бүлэгт байгаа эсэхийг Union-Find бүтэц хурдан хэлж өгнө.

Нэр томьёо ба тэмдэглэгээ

MST
Minimum spanning tree: бүх node-ыг холбосон, нийт жин нь хамгийн бага tree. Яг n − 1 edge-тэй.
p[x]
x node-ын бүлэг доторх эцэг. p[x] == x бол x бол бүлгийн толгой.
find(x)
x-ийн бүлгийн толгойг олдог function. p[x] = find(p[x]) нь замыг шахаж, дараагийн удаа хурдан болгоно.
cycle
Эхэлсэн node руугаа буцаж ирдэг зам. Tree-д cycle байхгүй.
cnt, total
Авсан edge-ийн тоо ба тэдгээрийн нийт жин.
4125367241бүлэг 12бүлэг 23бүлэг 34бүлэг 45бүлэг 56бүлэг 6
total = 0cnt = 0p[1..6] = 1 2 3 4 5 6
e: оролтын дарааллаар
1–2 (4)1–3 (1)2–3 (2)2–4 (5)2–5 (3)3–5 (6)4–5 (7)4–6 (2)5–6 (4)

Бүх node-ыг холбодог, нийт жин нь хамгийн бага edge-үүдийг сонгоно. Эхэндээ node бүр өөрөө тусдаа бүлэг: p[i] = i.

Алхам 1 / 17
Хурд
  • Шалгаж буй edge
  • Сая нийлсэн бүлэг
  • Tree-д орсон edge
  • Cycle үүсгэх тул алгассан
  • Minimum spanning tree (MST)
Слайд 1 / 7

Бүх хотыг холбоё

Бүх хотыг замаар холбоё, гэхдээ аль болох хямдаар. Edge-ийн жин бол тэр замын үнэ. Бүх node-ыг холбосон хамгийн хямд tree-г minimum spanning tree (MST) гэдэг.

kruskal.cpp
#include <bits/stdc++.h>
using namespace std;
int n, m, cnt, p[100005];
long long total;
array<int, 3> e[200005];
int find(int x) {
if (p[x] == x) return x;
return p[x] = find(p[x]);
}
int main() {
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
e[i] = {w, u, v};
}
for (int i = 1; i <= n; i++) p[i] = i;
sort(e, e + m);
for (int i = 0; i < m; i++) {
auto [w, u, v] = e[i];
if (find(u) != find(v)) {
total += w;
cnt++;
p[find(u)] = find(v);
}
}
cout << (cnt == n - 1 ? total : -1) << '\n';
return 0;
}

Юунд хэрэгтэй вэ?

Бүх node-ыг холбосон, нийт жин нь хамгийн бага tree-г (MST) олно. Жишээ нь хотуудыг хамгийн хямд замаар, кабелиар холбох. Greedy арга ба Union-Find бүтцийг хамт хэрэглэдэг сонгодог жишээ.

Яаж ажилладаг вэ?

1. Edge бүрийг {w, u, v} хэлбэрээр хадгалж, жингээр нь sort хийнэ. 2. Эхэндээ node бүр тусдаа бүлэг: p[i] = i. 3. Edge бүрийн хоёр үзүүрийн бүлгийн толгойг find() ашиглан олно. 4. Толгой нь өөр бол edge-ийг авч (total += w), хоёр бүлгийг нэгтгэнэ: p[find(u)] = find(v). 5. Толгой нь ижил бол edge cycle үүсгэх тул алгасна. 6. n − 1 edge авсан бол хариу нь total. Үгүй бол graph салангид тул -1. Оролт: эхний мөрөнд n m, дараагийн m мөрөнд «u v w» (чиглэлгүй edge, node-ууд 1…n).

Яагаад зөв, хэр хурдан бэ?

Хамгийн хямд edge нь хоёр бүлгийг холбож байвал түүнийг авахад алдахгүй. Өөр ямар ч MST эдгээр хоёр бүлгийг ямар нэг edge-ээр холбох ёстой. Тэр edge-ийг манай хямд edge-ээр сольвол нийт жин нэмэгдэхгүй. Энэ солих санаагаар Greedy сонголт бүр зөв гэдгийг харуулдаг.

Sort O(m log m), find бараг O(1). Нийт O(m log m). m = 200 000 бол 3.5 сая орчим харьцуулалт.

Түгээмэл алдаа

  • total-ийг int-ээр хадгалах. 10⁵ edge, жин 10⁹ бол нийлбэр int-ээс хэтэрнэ. Кодонд long long.
  • Edge-ийг {u, v, w} гэж хадгалаад sort хийх. Тэгвэл жингээр биш, u-гаар эрэмбэлэгдэнэ. {w, u, v} дарааллаар хадгал.
  • Graph салангид байхад нийт жинг хэвлэх. cnt == n - 1 эсэхийг шалгаж, үгүй бол -1.
  • p[i] = i-гаар эхлүүлэхээ мартах.

Хязгаарын тохиолдол

  • n = 1, m = 0: cnt == 0 == n - 1 тул хариу 0.
  • Graph салангид: cnt < n - 1, хариу -1.
  • Ижил жинтэй edge-үүд: MST олон байж болно, гэхдээ нийт жин нь үргэлж ижил.

Өөрийгөө шалга

  1. n node-той graph-ын MST хэдэн edge-тэй вэ?

    Хариу харах

    n − 1.

  2. 4 node, бүх хос хооронд жин 1-тэй edge (6 edge) байвал хариу хэд вэ?

    Хариу харах

    3. Ямар ч 3 edge-тэй tree тохирно.

  3. Edge-ийн хоёр үзүүрийн find ижил гарвал юу хийх вэ?

    Хариу харах

    Алгасна. Хоёр үзүүр аль хэдийн холбогдсон тул авбал cycle үүснэ.

Гурван дадлага

Hint-ээ нээхээс өмнө өөрөө оролдоорой.

  1. 1.Анимацийн жишээ graph дээр Kruskal ямар edge-үүдийг авахыг дарааллаар нь бич.

    Hint харах

    Эхлээд жингээр sort хий. Ижил жинтэй бол u, дараа нь v-гээр.

    Хариу ба тайлбар

    1–3 (1), 2–3 (2), 4–6 (2), 2–5 (3), 1–2 (4)-ийг алгасна, 5–6 (4)-ийг авна. Нийт 12.

  2. 2.Нийт жин нь хамгийн их tree-г (maximum spanning tree) ол.

    Hint харах

    Зөвхөн нэг мөр өөрчлөгдөнө.

    Хариу ба тайлбар

    Edge-үүдийг буурахаар sort хийнэ: sort(e, e + m, greater<>()). Жишээ graph дээр 26.

  3. 3.Graph хэдэн connected component-оос тогтохыг Kruskal-ын кодоор ол.

    Hint харах

    Авсан edge бүр хоёр бүлгийг нэг болгодог.

    Хариу ба тайлбар

    Эхэндээ n бүлэг, авсан edge бүр нэгээр цөөлнө. Хариу n - cnt.

Жишээ

Оролт

6 9
1 2 4
1 3 1
2 3 2
2 4 5
2 5 3
3 5 6
4 5 7
4 6 2
5 6 4

Гаралт

12

Одоо өөрөө бодоод үз

Бодлого

Хичээл

Энэ сэдвийн хичээл удахгүй нэмэгдэнэ.