Бүлэг бүрийг нэг root-ээр төлөөлүүлдэг бүтэц. Хоёр бүлгийг нэгтгэх, хоёр зүйл нэг бүлэгт байгаа эсэхийг маш хурдан хариулна.

IntermediateХугацаа: O(log n) дунджаар, нэг үйлдэлдСанах ой: O(n)
HackerRank дээр бодох

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

5 node байна. Үйлдлүүд: 1-2, 3-4, 1?4, 2-3, 1?4.

Эхний хоёр үйлдлээр {1, 2}, {3, 4} гэсэн бүлэг үүснэ. 1?4 асуухад root нь өөр тул NO. 2-3 нь хоёр бүлгийг нийлүүлнэ. Дахин 1?4 асуухад YES. Гаралт: NO, YES.

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

Энгийн арга: node бүрт бүлгийн дугаар g[i] хадгалах. Асуух нь хурдан, g[a] == g[b]. Харин нэгтгэх бүрт нэг бүлгийн бүх node-ын дугаарыг солихын тулд бүх node-ыг гүйнэ. n = q = 100 000 бол 10 тэрбум үйлдэл.

Гол санаа: бүлэг бүрийг tree хэлбэрээр хадгалах. Node бүр нэг "дээд" node-ыг заана (p[v]). Сумыг дагаж явсаар root-д хүрнэ. Нэгтгэхэд зөвхөн нэг root-ийг нөгөө рүү заалгахад л хангалттай. find явахдаа замдаа таарсан node-уудыг root рүү шууд заалгадаг тул tree намхан хэвээр үлдэнэ.

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

p[v]
v-гийн заадаг node (parent). p[v] == v бол v нь root.
root
Бүлгийн төлөөлөгч. Хоёр node-ын root ижил бол нэг бүлэгт байна.
find(v)
v-гийн root-ийг олно.
path compression
return p[v] = find(p[v]); буюу замдаа таарсан node бүрийг root рүү шууд заалгах.
t, a, b
t = 0 бол a, b-гийн бүлгийг нэгтгэнэ. t = 1 бол нэг бүлэгт байгаа эсэхийг асууна.
12345678

8 node байна. Сум нь «би түүнийг дагадаг» гэсэн утгатай. Хэнийг ч дагадаггүй node бол бүлгийн root. Root нь ижил бол хоёр node нэг бүлэгт байна.

Алхам 1 / 22
Хурд
  • Бүлгийн root (p[i] = i)
  • a ба b
  • Олсон root x, y
  • Замдаа таарсан
  • p шинэчлэгдсэн
  • Нэг бүлэг (YES)
Слайд 1 / 7

Бүлэг бүлгээрээ

Хүүхдүүд бүлэг болж тоглож байна. Бүлэг бүр нэг ахлагчтай. Бид ахлагчийг root гэж нэрлэе. Хоёр хүүхэд нэг бүлэгт байгаа эсэхийг root-ээр нь мэднэ.

union-find.cpp
#include <bits/stdc++.h>
using namespace std;
int n, q, p[100005];
int find(int v) {
if (p[v] == v) return v;
return p[v] = find(p[v]);
}
int main() {
cin >> n >> q;
for (int i = 1; i <= n; i++) p[i] = i;
while (q--) {
int t, a, b;
cin >> t >> a >> b;
int x = find(a), y = find(b);
if (t == 1) {
cout << (x == y ? "YES" : "NO") << '\n';
} else if (x != y) {
p[x] = y;
}
}
return 0;
}

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

«Эдгээрийг нэгтгэ» ба «энэ хоёр нэг бүлэгт байна уу?» гэсэн олон асуултад хурдан хариулна. Connected component тоолох, Kruskal зэрэгт ашигладаг.

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

1. Эхэндээ p[i] = i: node бүр өөрөө өөрийнхөө root. 2. find(v): p[v] = v бол v нь root. Үгүй бол сумаа дагаж root-ийг олоод, p[v]-д root-ийг бичнэ. Үүнийг path compression (замыг товчлох) гэдэг. 3. Нэгтгэх (t = 0): x = find(a), y = find(b). Root нь өөр бол p[x] = y. 4. Асуух (t = 1): root нь ижил бол YES, өөр бол NO. Оролт: эхний мөрөнд n ба q, дараа нь q мөрөнд «t a b».

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

Бүлэг бүр яг нэг tree, root нь p[v] = v байх ганц node. Нэгтгэх үед зөвхөн root-ийн p өөрчлөгддөг тул сумнууд хэзээ ч тойрог үүсгэхгүй, find үргэлж root-д хүрнэ. Path compression нь node-ын бүлгийг өөрчлөхгүй, зөвхөн замыг богиносгоно.

Path compression-тэй үед q үйлдэл нийтдээ ойролцоогоор O(q log n) хугацаа зарцуулна, практик дээр бараг O(1). n = q = 200 000 бол хормын дотор дуусна. Санах ой O(n).

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

  • Root-ийг биш node-ыг өөрийг нь холбох: p[a] = b. a-гийн бүлгийн бусад node салж үлдэнэ. Үргэлж p[find(a)] = find(b).
  • p[i] = i гэж эхлүүлэхээ мартах. p[i] нь 0 хэвээр үлдвэл бүх node байхгүй node 0-ийг заана.
  • Path compression-гүй return find(p[v]); гэж бичих. Урт гинж үүсэж, find нь O(n) болно.

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

  • a == b: асуухад үргэлж YES, нэгтгэхэд юу ч өөрчлөгдөхгүй.
  • Аль хэдийн нэг бүлэгт байгаа хоёрыг нэгтгэх: x == y тул p өөрчлөгдөхгүй.
  • Асуух үйлдэл огт байхгүй: юу ч хэвлэхгүй.

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

  1. 1-2, 2-3, 3-4 гэж нэгтгээд 1?4 асуув. Асуултын дараа p[1] хэд вэ?

    Хариу харах

    4. Гинж 1 → 2 → 3 → 4 үүссэн. find(1) явахдаа 1, 2, 3 бүгдийг 4 рүү шууд заалгана.

  2. Бүлгийн тоог яаж мэдэх вэ?

    Хариу харах

    p[i] == i байх i-н тоо. Root бүр нэг бүлэг.

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

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

  1. 1.Animation-ы жишээ үйлдлүүдийн хариуг гараар ол: 1-2, 3-4, 2-4, 1?3, 5-6, 7-8, 6-8, 5?1, 5-3, 7?2.

    Hint харах

    1?3 асуухад {1, 2, 3, 4} аль хэдийн нэг бүлэг болсон байна.

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

    YES, NO, YES. 5-3 үйлдлийн дараа бүх 8 node нэг бүлэгт орно.

  2. 2.Бүлэг бүрийн хэмжээг хадгалж, жижиг бүлгийг том руу нь нэгтгэдэг болго.

    Hint харах

    sz[i] = 1-ээр эхлүүлээд, нэгтгэхдээ sz-ийг нэм.

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

    if (sz[x] > sz[y]) swap(x, y); p[x] = y; sz[y] += sz[x];. Path compression-тэй хамт бол үйлдэл бүр бараг O(1).

  3. 3.Edge-үүдийг нэг нэгээр нь нэмэхэд аль edge cycle үүсгэхийг ол.

    Hint харах

    Edge нэмэхийн өмнө хоёр төгсгөлийн root-ийг харьцуул.

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

    find(u) == find(v) бол u, v аль хэдийн холбоотой тул энэ edge cycle үүсгэнэ. Эс бол нэгтгэнэ. Kruskal алгоритм яг ингэж ажилладаг.

Жишээ

Оролт

8 10
0 1 2
0 3 4
0 2 4
1 1 3
0 5 6
0 7 8
0 6 8
1 5 1
0 5 3
1 7 2

Гаралт

YES
NO
YES

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

Бодлого

Хичээл

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