Устгавал graph хуваагдах node-уудыг (articulation point) нэг DFS-ээр, tin ба low ашиглан олох арга.

Advanced & LegendХугацаа: O(n + m)Санах ой: O(n + m)

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

4 node, edge нь 1-2, 2-3, 3-1, 3-4. Аль node-ыг устгавал graph хуваагдах вэ?

Node 3-ыг устгавал node 4 бусдаасаа тасарна. Node 1 эсвэл 2-ыг устгахад үлдсэн node-ууд холбоотой хэвээр. Хариу: нэг articulation point, node 3.

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

Энгийн арга бол node бүрийг нэг нэгээр устгаад DFS-ээр холбоотой эсэхийг шалгах. n удаа DFS, O(n · (n + m)).

Гол санаа нь Bridges-тэй ижил: tin ба low. Child v-гийн subtree-гээс u-г тойроод дээш гарах back edge байхгүй бол (low[v] ≥ tin[u]) u устахад v тасарна. Root-ийн дээр node байхгүй тул root-д өөр дүрэм: DFS tree-д 2 буюу түүнээс олон child-тай бол articulation point.

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

articulation point
Устгавал graph-ын component-ын тоо нэмэгдэх node. "Cut vertex" ч гэдэг.
tin[u], low[u]
Bridges-тэй ижил: орсон дугаар ба subtree-гээс back edge-ээр хүрч болох хамгийн бага tin.
kids
DFS tree-д node u-гийн child-ын тоо. Зөвхөн root-д хэрэгтэй.
p == 0
u бол DFS-ийн root гэсэн үг.
1234567
дуудлагын stack
хоосон
cut (articulation point)
хоосон

Articulation point гэдэг нь устгавал graph хуваагдах node. DFS node бүрт хоёр тоо өгнө. tin нь тухайн node-д хэд дэх удаад орсныг хэлнэ. low нь node-ын доорх subtree-гээс back edge-ээр хүрч болох хамгийн бага tin. Node доор «tin/low» гэж харагдана.

Алхам 1 / 22
Хурд
  • Одоогийн node / edge
  • Дуудлагын stack дотор / back edge
  • Дууссан node / DFS tree-гийн edge
  • Сая олдсон
  • Articulation point
Слайд 1 / 6

Articulation point

Зарим хотыг хаавал бусад хотуудын хоорондох холбоо тасардаг. Graph дээр ийм node-ыг articulation point гэнэ.

articulation-points.cpp
#include <bits/stdc++.h>
using namespace std;
int n, m, timer, tin[100005], low[100005];
vector<int> g[100005];
bool cut[100005];
void dfs(int u, int p) {
tin[u] = low[u] = ++timer;
int kids = 0;
for (int v : g[u]) {
if (v == p) continue;
if (tin[v]) {
low[u] = min(low[u], tin[v]);
} else {
dfs(v, u);
kids++;
low[u] = min(low[u], low[v]);
if (p != 0 && low[v] >= tin[u]) {
cut[u] = true;
}
}
}
if (p == 0 && kids > 1) {
cut[u] = true;
}
}
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 (!tin[i]) {
dfs(i, 0);
}
}
int k = 0;
for (int i = 1; i <= n; i++) k += cut[i];
cout << k << '\n';
for (int i = 1; i <= n; i++) if (cut[i]) cout << i << ' ';
cout << '\n';
return 0;
}

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

Сүлжээнд аль хот, аль сервер унавал холбоо тасрахыг олно. Bridges-тэй бараг ижил санаатай.

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

1. DFS node бүрт tin дугаар өгч, low[u] = tin[u] гэж эхэлнэ. 2. Орсон node руу edge байвал low[u] = min(low[u], tin[v]). 3. Child v-гээс буцаад low[u] = min(low[u], low[v]). 4. u нь root биш бөгөөд low[v] ≥ tin[u] бол child v өөрийн subtree-гээс u-г тойроод дээш гарч чадахгүй. Тэгвэл u бол articulation point. 5. Root нь DFS tree-д 2 буюу түүнээс олон child-тай бол articulation point. 6. Articulation point-ын тоо, дараа нь тэдгээрийг хэвлэнэ. Оролт: n m, дараа нь m мөрөнд «u v» (чиглэлгүй edge, давхардалгүй).

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

Root биш u-г устгахад child v-гийн subtree u-гийн parent тал руу зөвхөн back edge-ээр л холбогдож чадна. low[v] ≥ tin[u] бол ийм back edge u-гийн дээд тал руу гардаггүй тул subtree тасарна. Root-ийн хувьд child бүрийн subtree хоорондоо зөвхөн root-оор дамжиж холбогддог: чиглэлгүй DFS-д хоёр өөр subtree-г холбосон edge гардаггүй. Тиймээс 2+ child бол root устахад тэд сална.

Нэг DFS, хугацаа O(n + m).

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

  • Root-д ч low[v] >= tin[u] дүрмийг хэрэглэх. Root-д энэ үргэлж үнэн тул ганц child-тай root-ыг буруугаар articulation point гэнэ.
  • kids-ийг хөршийн тоогоор тоолох. Зөвхөн DFS tree-гийн child, өөрөөр хэлбэл dfs(v)-г дуудсан удаа л тоологдоно.
  • Нэг node-ыг олон удаа тоолох. cut[u] = true гэж тэмдэглээд эцэст нь тоолбол давхардахгүй.

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

  • Гинж 1-2-3: дунд node 2 articulation point, хоёр үзүүр нь биш.
  • Star 1-2, 1-3: root 1 хоёр child-тай тул articulation point.
  • Cycle: аль ч node-ыг устгасан үлдсэн нь гинж болж холбоотой үлдэнэ, хариу 0.

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

  1. 1-2, 2-3, 3-4, 4-1 cycle-д хэдэн articulation point байна вэ?

    Хариу харах

    0.

  2. Animation-ы "Root нь articulation point" жишээнд (1-2, 1-3, 2-3, 1-4, 4-5) root 1 хэдэн child-тай вэ?

    Хариу харах

    2. Нэг нь node 2 (2, 3-ын хэсэг), нөгөө нь node 4 (4, 5-ын хэсэг). Node 3-т 2-оор дамжиж хүрсэн тул тусдаа child биш.

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

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

  1. 1.6 node, edge нь 1-2, 2-3, 3-1, 3-4, 4-5, 5-6, 6-4. Код юу хэвлэх вэ?

    Hint харах

    Хоёр triangle-ыг холбосон edge-ийн хоёр үзүүрийг бод.

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

    2, дараа нь 3 4. Node 3 устахад {1, 2} тасарна, node 4 устахад {5, 6} тасарна.

  2. 2.Articulation point бүрийг устгахад graph хэдэн хэсэгт хуваагдахыг хэвлэдэг болго.

    Hint харах

    low[v] ≥ tin[u] нөхцөл хангагдах child бүр тусдаа хэсэг болж тасарна.

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

    Root биш u-д нөхцөл хангагдсан child-ын тоог c гэвэл u устахад c + 1 хэсэг болно (дээд тал нэмэгдэнэ). Root-д kids хэсэг болно.

  3. 3.Graph-т bridge байхгүй ч articulation point байж болох уу? Жишээ гарга.

    Hint харах

    Нэг node дээр залгагдсан хоёр cycle-ыг зур.

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

    Тийм. 1-2, 2-3, 3-1, 3-4, 4-5, 5-3: node 3 articulation point, гэхдээ edge бүр cycle-д орсон тул bridge байхгүй.

Жишээ

Оролт

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

Гаралт

3
3 4 6