Graph хэдэн connected component-оос (холбоотой хэсгээс) тогтохыг DFS-ээр тоолох арга.

Pre-IntermediateХугацаа: O(n + m)Санах ой: O(n + m)
HackerRank дээр бодох

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

6 node-той graph-т 1-2, 2-3, 4-5 гэсэн гурван edge байна. Хэдэн тусдаа хэсэг байна вэ?

Node 1-ээс 2, 3 хүрнэ: энэ нь эхний component. Node 4-өөс 5 хүрнэ: хоёр дахь component. Node 6 ганцаараа: гурав дахь component. Хариу 3, comp array нь 1 1 1 2 2 3.

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

Энгийн арга бол node хос бүрийн хувьд "хоорондоо path байна уу?" гэж тусад нь хайх. n = 1000 бол хагас сая хос, хос бүрт бүтэн хайлт хийнэ. Хэт удаан.

Гол санаа: нэг node-оос DFS эхлүүлбэл тэр node-ын component-ын бүх node-д нэг дор хүрнэ. Тиймээс node-уудыг дарааллаар нь харж, хараахан тэмдэглэгдээгүй node олдох бүрт шинэ component эхлүүлээд DFS явуулна. Ингэхэд node бүрт яг нэг удаа орно.

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

connected component
Хоорондоо path-аар холбоотой node-уудын хамгийн том бүлэг. Монголоор "холбоотой хэсэг".
comp[u]
Node u аль component-од орсныг заана. 0 бол хараахан ороогүй.
cnt
Одоогоор олдсон component-ын тоо. Шинэ component эхлэх бүрт 1-ээр нэмэгдэнэ.
dfs(u)
Node u-д орж, тэмдэглэгдээгүй хөрш бүр рүү гүнзгийрч орох recursive function.
12345678
cnt = 0
дуудлагын stack
хоосон

Graph хэдэн connected component-оос тогтох вэ? Node-уудыг 1, 2, … n гэж дарааллаар нь шалгана. Аль ч component-од ороогүй node олдвол тэндээс DFS эхлүүлж, хүрч болох бүх node-ыг нэг component гэж тэмдэглэнэ.

Алхам 1 / 30
Хурд
  • Одоогийн node / edge
  • Шинэ component-ын эхлэл
  • Одоогийн component-од орсон
  • Өмнөх component-ууд / DFS-ийн явсан edge
Слайд 1 / 6

Хэдэн арал байна?

Далайд хэдэн арал байгааг тоолъё. Нэг арлын хотууд хоорондоо замаар холбоотой, харин өөр арал руу зам байхгүй. Graph дээр ийм арлыг connected component гэнэ.

connected-components.cpp
#include <bits/stdc++.h>
using namespace std;
int n, m, cnt, comp[100005];
vector<int> g[100005];
void dfs(int u) {
comp[u] = cnt;
for (int v : g[u]) {
if (!comp[v]) {
dfs(v);
}
}
}
int main() {
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
for (int i = 1; i <= n; i++) {
if (!comp[i]) {
cnt++;
dfs(i);
}
}
cout << cnt << '\n';
for (int i = 1; i <= n; i++) cout << comp[i] << ' ';
cout << '\n';
return 0;
}

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

Ямар хотууд хоорондоо замаар холбоотой, аль нь тусдаа вэ гэдгийг олно. Олимпиадын graph бодлогын эхний алхам ихэвчлэн component-уудыг олох байдаг.

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

1. comp[i] = 0 бол node i аль ч component-од ороогүй гэсэн үг. 2. Node-уудыг 1, 2, … n гэж дарааллаар нь шалгана. 3. Component-од ороогүй node олдвол cnt-г 1-ээр нэмээд тэндээс DFS эхлүүлнэ. 4. DFS-ийн хүрсэн бүх node-д comp = cnt гэж бичнэ. 5. Эцэст нь cnt бол component-ын тоо, comp бол node бүрийн component-ын дугаар. Оролт: n m, дараа нь m мөрөнд «u v» (чиглэлгүй edge, node 1…n).

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

DFS эхэлсэн node-оос path-аар хүрч болох бүх node-д заавал очно, өөр component-ын node-д хэзээ ч очихгүй. Тиймээс нэг DFS яг нэг component-ыг бүтнээр нь тэмдэглэнэ. Main дотор тэмдэглэгдээгүй node олдох бүрт cnt нэмэгддэг тул cnt нь component-ын тоотой тэнцүү.

Node бүрт нэг удаа орж, edge бүрийг хоёр талаас нь нэг нэг удаа харна. Хугацаа O(n + m). n = 100 000, m = 200 000 бол хэдэн зуун мянган үйлдэл л болно.

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

  • Чиглэлгүй edge-ийг нэг л тал руу нь нэмэх. g[u].push_back(v) хийгээд g[v].push_back(u)-г мартвал DFS зарим node-д хүрэхгүй.
  • Маш урт гинж (n = 100 000) дээр recursive DFS stack overflow өгч болно. Тэгвэл queue-тэй BFS эсвэл өөрийн stack ашигла.
  • Edge-гүй node-ыг мартах. Ийм node ганцаараа нэг component тул cnt-д заавал орно.

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

  • m = 0: node бүр тусдаа component, хариу n.
  • Бүх node холбоотой: нэг л DFS бүгдийг тэмдэглэнэ, хариу 1.
  • Давхар edge (1-2 хоёр удаа): хоёр дахь удаад хөрш нь аль хэдийн тэмдэглэгдсэн тул алгасна, хариу өөрчлөгдөхгүй.

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

  1. 5 node-той, edge огт байхгүй graph хэдэн component-той вэ?

    Хариу харах

    5. Node бүр ганцаараа нэг component.

  2. Яагаад comp[i] != 0 үед node i-д шинэ DFS эхлүүлэхгүй вэ?

    Хариу харах

    Тэр node өмнөх DFS-ээр тэмдэглэгдсэн, өөрөөр хэлбэл түүний component аль хэдийн тоологдсон.

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

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

  1. 1.7 node, edge нь 1-4, 2-5, 4-7, 3-6. Код юу хэвлэхийг гараар ол.

    Hint харах

    Node 1, 2, 3 гэж дарааллаар нь шалга. Тэмдэглэгдээгүй node бүрээс шинэ дугаар эхэлнэ.

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

    Эхний мөрөнд 3, хоёр дахь мөрөнд 1 2 3 1 2 3 1. Component-ууд нь {1, 4, 7}, {2, 5}, {3, 6}.

  2. 2.Хамгийн том component хэдэн node-той болохыг хэвлэдэг болго.

    Hint харах

    Main доторх loop дууссаны дараа comp array-аар нэг явж, дугаар бүр хэдэн удаа гарсныг тоол.

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

    vector<int> sz(cnt + 1); үүсгээд for (int i = 1; i <= n; i++) sz[comp[i]]++; гэнэ. Хариу нь sz-ийн хамгийн их утга.

  3. 3.Graph-ыг бүхэлд нь холбоотой болгохын тулд хамгийн цөөндөө хэдэн edge нэмэх вэ?

    Hint харах

    Нэг шинэ edge хоёр component-ыг нэг болгож чадна.

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

    cnt - 1. Component бүрээс нэг node сонгоод тэднийг гинж шиг холбоход хүрнэ. Үүнээс цөөн edge-ээр бүх component-ыг нэгтгэх боломжгүй.

Жишээ

Оролт

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

Гаралт

3
1 1 1 2 2 3 3 3

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

Бодлого

Хичээл

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