Чиглэлтэй graph-ыг бие бие рүүгээ хүрч чаддаг node-уудын бүлэгт (SCC) хуваах арга. Хоёр удаа DFS хийнэ.

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

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

Чиглэлтэй graph: 1 → 2, 2 → 1, 2 → 3. Node 1, 2 бие бие рүүгээ явж чадна, тэгэхээр нэг SCC. Node 3-т очиж болох ч буцах edge алга, тиймээс 3 тусдаа SCC.

Хариу 2, node бүрийн SCC нь 1 1 2.

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

Энгийн арга бол node бүрээс DFS хийж "хэнд хүрч чадах вэ" гэдгийг олоод, хоёр талаасаа хүрдэг хосуудыг нэгтгэх. n удаа DFS, O(n · (n + m)).

Kosaraju-гийн санаа: эхний DFS-ээр node бүр хэзээ дууссаныг (order) тэмдэглэнэ. Хамгийн сүүлд дууссан node заавал "эхний" SCC-д байдаг: түүн рүү өөр SCC-гээс edge ирдэггүй. Дараа нь бүх edge-ийг эргүүлээд, order-ын урвуу дарааллаар DFS хийхэд DFS бүр яг нэг SCC-д хүрээд зогсоно.

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

SCC
Strongly Connected Component: дурын хоёр node нь бие бие рүүгээ path-тай байх хамгийн том бүлэг.
g, rg
g бол анхны graph, rg бол бүх edge-ийн чиглэлийг эргүүлсэн graph.
order
Эхний DFS-д node-ууд дууссан дараалал. Урвуулсны дараа хамгийн сүүлд дууссан нь эхэнд байна.
comp[u]
Node u-гийн SCC-гийн дугаар. 0 бол хараахан будаагүй.
condensation
SCC бүрийг нэг node болгож шахсан graph. Энэ graph-т cycle байдаггүй (DAG).
1234567
дуудлагын stack
хоосон
order — дууссан дараалал
хоосон

7 node, 9 чиглэлтэй edge-тэй graph. Edge-ийн чиглэлээр бие бие рүүгээ хүрч чаддаг node-уудын бүлгийг SCC гэнэ. Эхлээд DFS хийж, node бүр хэд дэх удаад дууссаныг тэмдэглэнэ.

Алхам 1 / 27
Хурд
  • Одоогийн node ба edge
  • DFS дотор, хараахан дуусаагүй
  • Дууссан node / өмнөх SCC
  • Сая будсан node
  • Одоо будаж буй SCC
Слайд 1 / 6

Хоорондоо хүрч чаддаг бүлэг

Чиглэлтэй edge бол нэг чиглэлийн зам. Хоёр node нэг нэгэндээ хүрч, бас буцаж ирж чаддаг бол тэд нэг бүлэгт орно. Ийм бүлгийг Strongly Connected Component (SCC) гэнэ.

scc-kosaraju.cpp
#include <bits/stdc++.h>
using namespace std;
int n, m, cnt, comp[100005];
bool used[100005];
vector<int> g[100005], rg[100005], order;
void dfs1(int u) {
used[u] = true;
for (int v : g[u]) {
if (!used[v]) {
dfs1(v);
}
}
order.push_back(u);
}
void dfs2(int u) {
comp[u] = cnt;
for (int v : rg[u]) {
if (comp[v] == 0) {
dfs2(v);
}
}
}
int main() {
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
rg[v].push_back(u);
}
for (int i = 1; i <= n; i++) {
if (!used[i]) {
dfs1(i);
}
}
reverse(order.begin(), order.end());
for (int u : order) {
if (comp[u] == 0) {
cnt++;
dfs2(u);
}
}
cout << cnt << '\n';
for (int i = 1; i <= n; i++) cout << comp[i] << ' ';
return 0;
}

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

Нэг чиглэлтэй замтай graph-т хэн хэн рүүгээ очиж, буцаж ирж чадахыг олно. SCC бүрийг нэг node болгож шахвал cycle-гүй graph (DAG) үүсэх тул олон бодлого хялбар болдог. 2-SAT ч үүн дээр тулгуурладаг.

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

1. Бүх node-оор DFS хийнэ. Node бүх хөршөө үзэж дуусмагц order жагсаалтын төгсгөлд нэмэгдэнэ. 2. Order жагсаалтыг урвуулна. Хамгийн сүүлд дууссан node эхэнд гарна. 3. Бүх edge-ийн чиглэлийг эсрэгээр нь эргүүлсэн graph (rg) бэлдэнэ. 4. Order-ын дарааллаар будаагүй node бүрээс rg дээр DFS хийнэ. Нэг DFS-ийн хүрсэн бүх node нэг SCC. 5. SCC-гийн тоо ба node бүрийн SCC-г хэвлэнэ. SCC-гийн дугаар edge-ийн чиглэлийн дагуу өсдөг. Оролт: n m, дараа нь m мөрөнд «u v» (u → v чиглэлтэй edge).

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

Хоёр SCC A, B-ийн хооронд A → B edge байвал A-ийн хамгийн сүүлд дууссан node B-ийн бүх node-оос хойно дуусдаг. Тиймээс урвуулсан order-ын эхний node condensation-ы "эх" SCC-д байна. Эргүүлсэн graph дээр тэр SCC-гээс гарах edge нь зөвхөн аль хэдийн будагдсан SCC руу заадаг. Иймээс хоёр дахь DFS бүр яг нэг SCC-г будаад зогсоно.

Хоёр DFS, хугацаа O(n + m). n = 100 000, m = 200 000 дээр хурдан ажиллана.

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

  • Хоёр дахь DFS-ийг rg биш g дээр хийх. Тэгвэл DFS нэг SCC-гээс гарч бусад SCC руу орж, хэд хэдэн SCC нэг болж будагдана.
  • order-ыг урвуулахаа мартах. Урвуулахгүй бол "сүүлийн" SCC-гээс эхэлж, мөн л буруу хариу гарна.
  • Recursive DFS-ийн гүн. n = 100 000 урт гинж дээр stack overflow болж болно.

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

  • Cycle огт байхгүй (DAG): node бүр тусдаа SCC, хариу n.
  • Нэг том cycle: бүх node нэг SCC, хариу 1.
  • Edge байхгүй: хариу n, comp нь 1 2 … n.

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

  1. 1 → 2, 2 → 3, 3 → 4 гинж хэдэн SCC-тэй вэ?

    Хариу харах

    4. Буцах edge байхгүй тул node бүр тусдаа.

  2. 1 → 2, 2 → 3, 3 → 1, 3 → 4 graph-т код юу хэвлэх вэ?

    Хариу харах

    2, дараа нь 1 1 1 2. {1, 2, 3} нэг cycle, node 4 тусдаа.

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

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

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

    Hint харах

    Cycle-уудыг олоод, тэдгээрийн хооронд буцах edge байгаа эсэхийг хар.

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

    2 SCC: {1, 2, 3} ба {4, 5, 6}. Код 1 1 1 2 2 2 хэвлэнэ.

  2. 2.Condensation graph-т хэдэн "эх" SCC (өөр SCC-гээс edge ирдэггүй) байгааг тоол.

    Hint харах

    Edge u → v бүрт comp[u] != comp[v] бол comp[v]-д орох edge байна гэж тэмдэглэ.

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

    bool in[cnt + 1] үүсгэнэ. comp[u] != comp[v] edge бүрт in[comp[v]] = true. in нь false байх SCC-гийн тоо хариу.

  3. 3.Хамгийн цөөндөө хэдэн edge нэмбэл бүх graph нэг SCC болох вэ?

    Hint харах

    Condensation-ы эх SCC-гийн тоо ба "төгсгөл" SCC-гийн (гарах edge-гүй) тоог ол.

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

    cnt = 1 бол 0. Үгүй бол эх SCC-гийн тоо ба төгсгөл SCC-гийн тооны ихийг нь хэвлэнэ.

Жишээ

Оролт

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

Гаралт

3
1 1 1 2 2 2 3