Website Summary Files Commits Branches @commit @diff @stats
path: root / Seminar11 / find-cycle.cpp
diff options
context:
space:
mode:
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