Чиглэлтэй graph-т cycle байгаа эсэхийг DFS ба гурван өнгөөр олох арга.

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

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

Чиглэлтэй graph: 1 → 2, 2 → 3, 3 → 1. Node 1-ээс 2, 3-аар дамжаад буцаад 1 дээр ирнэ. Cycle бий, хариу YES.

Харин 1 → 2, 1 → 3, 2 → 3 дээр node 3-т хоёр өөр замаар ирж болно, гэхдээ 3-аас гарах edge алга. Эхэлсэн газартаа буцаж ирэх боломжгүй тул хариу NO.

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

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

Гол санаа: нэг DFS хангалттай. Node бүрт гурван өнгө өгнө. color = 1 нь "одоо явж буй path дээр байна" гэсэн үг. Edge color = 1 node руу заавал бид path-ынхаа өмнөх node руу буцаж ирсэн, тэгэхээр cycle бий. color = 2 node-ын бүх замыг аль хэдийн шалгасан тул тийшээ дахин орох хэрэггүй.

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

color[u] = 0
Node u-д хараахан очоогүй.
color[u] = 1
Node u одоогийн DFS path дээр байна: dfs(u) эхэлсэн ч хараахан дуусаагүй.
color[u] = 2
dfs(u) бүрэн дууссан. u дээрээс эхлэх ямар ч path cycle рүү хүрэхгүй гэдгийг мэдэж авсан.
back edge
Одоогийн path дээрх node руу буцаж заасан edge. Яг ийм edge cycle үүсгэдэг.
1color=02color=03color=04color=05color=06color=0
дуудлагын stack
хоосон

Edge-ийн чиглэлийг дагаж явсаар эхэлсэн node руугаа буцаж ирж болох уу? Ийм path-ыг cycle гэнэ. Node бүр гурван өнгийн нэгтэй: color = 0 бол очоогүй, color = 1 бол одоогийн path дээр байгаа, color = 2 бол бүрэн дууссан.

Алхам 1 / 17
Хурд
  • Одоогийн node / edge
  • color = 1, одоогийн path дээр
  • color = 2, дууссан
  • Олдсон cycle
Слайд 1 / 6

Cycle байна уу?

Edge-ийн чиглэлийг дагаж явсаар эхэлсэн node руугаа буцаж ирж болох уу? Болдог бол graph cycle-тай.

cycle-detection.cpp
#include <bits/stdc++.h>
using namespace std;
int n, m, color[100005];
vector<int> g[100005];
void dfs(int u) {
color[u] = 1;
for (int v : g[u]) {
if (color[v] == 1) {
cout << "YES\n";
exit(0);
}
if (color[v] == 0) {
dfs(v);
}
}
color[u] = 2;
}
int main() {
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
}
for (int i = 1; i <= n; i++) {
if (color[i] == 0) {
dfs(i);
}
}
cout << "NO\n";
return 0;
}

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

Ажлууд бие биеэ тойруулж хүлээж байна уу, програмын модулиуд бие биеэсээ тойрч хамаарсан уу гэдгийг шалгана. Topological Sort хийхийн өмнө ихэвчлэн ашиглана.

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

1. color[u]: 0 бол очоогүй, 1 бол одоогийн path дээр, 2 бол бүрэн дууссан. 2. DFS node-д орохдоо color = 1 болгоно. 3. Edge бүрийн очих node-ыг шалгана. color = 1 бол бид path руугаа буцаж ирсэн: cycle бий, хариу YES. 4. color = 0 бол тийшээ гүнзгийрч орно, color = 2 бол алгасна. 5. Бүх edge-ээ шалгасан node-ыг color = 2 болгоно. 6. Бүх node дуусаад cycle олдоогүй бол NO. Оролт: n m, дараа нь m мөрөнд «u v» (u → v чиглэлтэй edge).

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

Cycle байвал DFS cycle-ын аль нэг node-д анх орох мөчид бусад нь color = 0 байна. DFS cycle-ыг дагаж явсаар cycle-ын сүүлийн node-д хүрээд эхний node руу заасан edge-ийг харна. Тэр үед эхний node color = 1 тул cycle заавал олдоно. Харин color = 2 node руу заасан edge cycle үүсгэхгүй: тэр node-оос одоогийн path руу буцах зам байсан бол түүнийг өмнө нь олох байсан.

Node бүрт нэг удаа орж, edge бүрийг нэг удаа харна. Хугацаа O(n + m).

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

  • Хоёр өнгө (очсон, очоогүй) л ашиглах. Тэгвэл 1 → 2, 1 → 3, 2 → 3 шиг cycle-гүй graph дээр node 3-т хоёр дахь удаа ирэхэд буруугаар YES гэнэ.
  • dfs дуусахад color[u] = 2 болгохоо мартах. Тэгвэл node 1 хэвээр үлдэж, дараа нь тийшээ заасан edge бүр cycle мэт харагдана.
  • Зөвхөн node 1-ээс DFS эхлүүлэх. Node 1-ээс хүрэхгүй хэсэгт cycle байж болно.

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

  • Edge байхгүй: бүх node шууд color = 2 болно, хариу NO.
  • Хоёр node хоорондоо 1 → 2, 2 → 1: энэ бол 2 урттай cycle, хариу YES.
  • DAG (cycle-гүй чиглэлтэй graph): хариу NO, Topological Sort хийж болно.

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

  1. 1 → 2, 1 → 3, 2 → 3 graph дээр node 3-ыг хоёр дахь удаа харахад өнгө нь хэд байх вэ?

    Хариу харах

    2. dfs(3) аль хэдийн дууссан тул алгасна, хариу NO.

  2. Cycle олдох мөчид дуудлагын stack дотор юу байна вэ?

    Хариу харах

    Cycle-ын бүх node, мөн cycle хүртэл хүрсэн path-ын node-ууд. Cycle нь stack доторх color = 1 node-оос stack-ийн хамгийн дээд node хүртэлх хэсэг.

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

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

  1. 1.1 → 2, 2 → 3, 3 → 4, 4 → 2. Ямар edge дээр cycle олдох вэ?

    Hint харах

    dfs(1), dfs(2), dfs(3), dfs(4) дараалан дуудагдана.

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

    dfs(4) дотор 4 → 2 edge-ийг шалгахад node 2 color = 1 байна. Cycle нь 2 → 3 → 4 → 2, хариу YES.

  2. 2.Cycle олдвол түүний node-уудыг хэвлэдэг болго.

    Hint харах

    dfs(v) дуудахын өмнө par[v] = u гэж хадгал. Cycle олдох үед u дээрээс par-аар ухарсаар v хүрнэ.

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

    color[v] == 1 үед for (int x = u; x != v; x = par[x]) гэж node-уудыг цуглуулж, v-г нэмээд урвуулна. Дээрх жишээнд 2 3 4 гарна.

  3. 3.Чиглэлгүй graph-т cycle байгаа эсэхийг шалгадаг болго.

    Hint харах

    Чиглэлгүй graph-т хүүхэд нь эцэг рүүгээ буцах edge-ийг cycle гэж тоолж болохгүй.

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

    dfs(u, p) гэж parent-ыг дамжуулаад v == p бол алгасна. Бусад үед аль хэдийн очсон node руу edge олдвол cycle бий. Эсвэл энгийнээр: нэг component-ын edge-ийн тоо node-ын тооноос багагүй бол cycle бий.

Жишээ

Оролт

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

Гаралт

YES