Устгавал graph хуваагдах edge-үүдийг (bridge) нэг DFS-ээр, tin ба low ашиглан олох арга.

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

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

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

1, 2, 3 нь triangle тул тэдний аль нэг edge устсан ч нөгөө хоёроор нь холбоотой хэвээр. Харин 3-4 устгавал node 4 тасарна. Хариу: нэг bridge, 3 4.

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

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

Гол санаа: нэг DFS хангалттай. DFS node бүрт орсон дугаар tin өгнө. low[u] нь u-гийн subtree-гээс back edge-ээр хүрч болох хамгийн бага tin. Child v-гийн subtree-гээс u эсвэл түүнээс дээш гарах edge байхгүй бол (low[v] > tin[u]) u-v edge л цорын ганц холбоо, тэгэхээр bridge.

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

bridge
Устгавал graph-ын component-ын тоо нэмэгдэх edge.
tin[u]
DFS node u-д хэд дэх удаад орсон дугаар.
low[u]
u-гийн subtree-гийн node-уудаас нэг back edge-ээр хүрч болох хамгийн бага tin.
back edge
DFS tree-д ороогүй, аль хэдийн орсон дээд node руу заасан edge.
p
u-д ирсэн parent node. Түүн рүү буцах edge-ийг алгасна.
1234567
дуудлагын stack
хоосон
res (bridge-үүд)
хоосон

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

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

Bridge гэж юу вэ?

Хоёр арлыг холбосон ганц гүүр нурвал арлууд хоорондоо салдаг. Graph дээр устгавал graph хуваагдах edge-ийг bridge гэнэ.

bridges.cpp
#include <bits/stdc++.h>
using namespace std;
int n, m, timer, tin[100005], low[100005];
vector<int> g[100005];
vector<pair<int, int>> res;
void dfs(int u, int p) {
tin[u] = low[u] = ++timer;
for (int v : g[u]) {
if (v == p) continue;
if (tin[v]) {
low[u] = min(low[u], tin[v]);
} else {
dfs(v, u);
low[u] = min(low[u], low[v]);
if (low[v] > tin[u]) {
res.push_back({min(u, v), max(u, 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 (!tin[i]) {
dfs(i, 0);
}
}
sort(res.begin(), res.end());
cout << res.size() << '\n';
for (auto [u, v] : res) cout << u << ' ' << v << '\n';
return 0;
}

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

Сүлжээний хамгийн эмзэг холбоосыг олно: аль кабель тасарвал холбоо салах вэ. Олимпиадын ахисан түвшний graph бодлогод түгээмэл.

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

1. DFS node бүрт орсон дарааллаар нь tin дугаар өгнө. Эхэндээ low[u] = tin[u]. 2. Аль хэдийн орсон v руу edge байвал low[u] = min(low[u], tin[v]). 3. Шинэ child v-гээс буцаж ирээд low[u] = min(low[u], low[v]). 4. low[v] > tin[u] бол child v өөрийн subtree-гээс u хүртэл ч хүрч чадахгүй. Тэгвэл u–v edge бол bridge. 5. Эцэст нь bridge-ийн тоо, дараа нь bridge бүрийг хэвлэнэ. Оролт: n m, дараа нь m мөрөнд «u v» (чиглэлгүй edge, давхардалгүй).

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

Чиглэлгүй graph-ын DFS-д tree edge болон back edge л байдаг. Tree edge u-v устахад v-гийн subtree тасрах эсэх нь subtree-гээс u-гийн дээд тал руу гарах back edge байгаа эсэхээс л хамаарна. low[v] яг үүнийг хадгалдаг: low[v] ≤ tin[u] бол тойрох зам бий, low[v] > tin[u] бол үгүй. Back edge өөрөө cycle дотор байдаг тул хэзээ ч bridge биш.

Нэг DFS, хугацаа O(n + m). n = 100 000, m = 200 000 дээр хурдан.

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

  • Parent руу буцах edge-ийг алгасахгүй байх. Тэгвэл low[v] үргэлж tin[u] болж, нэг ч bridge олдохгүй.
  • Нөхцөлийг >= гэж бичих. Bridge-д low[v] > tin[u], articulation point-д >=. Хольж болохгүй.
  • Back edge-д low[u] = min(low[u], low[v]) гэж бичих. Back edge-д tin[v] ашигладаг.
  • Давхар edge (1-2 хоёр удаа) байвал v == p гэж алгасах нь буруу. Тэгвэл edge-ийн дугаараар нь алгас.

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

  • Tree: cycle байхгүй тул бүх n - 1 edge bridge.
  • Нэг том cycle: bridge байхгүй, хариу 0.
  • Graph хэд хэдэн component-той: код node бүрээс шалгаж, tin = 0 бол шинэ DFS эхлүүлнэ.

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

  1. 1-2, 2-3, 3-4 гинжинд хэдэн bridge байна вэ?

    Хариу харах

    3. Tree-гийн бүх edge bridge.

  2. Жижиг жишээнд (1-2, 2-3, 3-1, 3-4) node 3-ын tin, low хэд вэ?

    Хариу харах

    tin[3] = 3, low[3] = 1. 3-1 back edge-ээр node 1 (tin = 1) хүрнэ.

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

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

  1. 1.6 node, edge нь 1-2, 2-3, 3-1, 3-4, 4-5, 5-6, 6-4. Хэдэн bridge байна вэ?

    Hint харах

    Хоёр triangle-ыг юу холбож байна вэ?

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

    1 bridge: 3 4. Triangle доторх edge бүр cycle-д орно.

  2. 2.Давхар edge-тэй graph дээр зөв ажилладаг болго.

    Hint харах

    g[u]-д хөршөөс гадна edge-ийн дугаарыг хадгал.

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

    g[u].push_back({v, i}) гээд dfs(u, pe)-д parent node-ын оронд ирсэн edge-ийн дугаар pe-г дамжуулна. id == pe үед л алгасна. Ингэхэд 1-2 хоёр удаа байвал аль нь ч bridge болохгүй.

  3. 3.Бүх bridge-ийг устгасны дараа үлдэх хэсгүүдийг (2-edge-connected component) тоол.

    Hint харах

    Bridge-үүдийг тэмдэглээд, тэднийг ашиглахгүйгээр Connected Components-ийг ажиллуул.

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

    Bridge бүрийг set-д хийнэ. Дараа нь bridge биш edge-ээр л DFS явуулж component тоолно. Хариу нь bridge-ийн тоо + 1-тэй тэнцүү (graph холбоотой бол).

Жишээ

Оролт

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

Гаралт

2
3 4
6 7