Website Summary Files Commits Branches @commit @diff @stats
path: root / Seminar11 / find-cycle.cpp
diff options
context:
space:
mode:
Commit3c72a02284dad4ddd9df1ff6910ed1a0a4550a30 (patch)
Author
 Stoycho Kyosev <stoycho.kk@gmail.com>
2024-12-22 13:19:05 -0500
Committer
 Stoycho Kyosev <stoycho.kk@gmail.com>
2024-12-22 13:19:05 -0500
Filese5921b4ff115ae1a1cd570559ea539ecae5a0962 /Seminar11/find-cycle.cpp
Data-structures-and-algorithms-3c72a02284dad4ddd9df1ff6910ed1a0a4550a30.tar
Data-structures-and-algorithms-3c72a02284dad4ddd9df1ff6910ed1a0a4550a30.tar.gz
Data-structures-and-algorithms-3c72a02284dad4ddd9df1ff6910ed1a0a4550a30.zip
Parentd8fb59b4d45197c9b3a2b100a3d94b1c2e92b2ef (diff)
Add seminar 10 and 11
1 files changed, 54 insertions, 0 deletions
-rw-r--r--Seminar11/find-cycle.cpp54
diff --git a/Seminar11/find-cycle.cpp b/Seminar11/find-cycle.cpp
new file mode 100644
index 0000000..cd5bd32
--- /dev/null
+++ b/Seminar11/find-cycle.cpp
@@ -0,0 +1,54 @@
+#include <iostream>
+#include <vector>
+#include <list>
+
+using graph = std::vector<std::list<int>>;
+
+enum class color : char
+{
+ white,
+ gray,
+ black
+};
+
+bool has_cycle_cc(const graph& g, int vertex, std::vector<color>& colors)
+{
+ const auto& adjacent = g[vertex];
+ colors[vertex] = color::gray;
+
+ for(int child : adjacent)
+ {
+ if(colors[child] == color::gray)
+ return true;
+
+ if(has_cycle_cc(g, child, colors))
+ return true;
+ }
+
+ colors[vertex] = color::black;
+ return false;
+}
+
+bool has_cycle(const graph& g)
+{
+ std::vector<color> colors(g.size(), color::white);
+
+ for(int vertex = 0; vertex < g.size(); vertex++)
+ {
+ if(colors[vertex] == color::white && has_cycle_cc(g, vertex, colors))
+ return true;
+ }
+ return false;
+}
+
+int main()
+{
+ graph g = {
+ /* 0 */ {1, 2},
+ /* 1 */ {3, 2},
+ /* 2 */ {},
+ /* 3 */ {2, 0}
+ }; // cycle: 0 -> 1 -> 3 -> 0
+
+ std::cout << has_cycle(g);
+} \ No newline at end of file