From 3c72a02284dad4ddd9df1ff6910ed1a0a4550a30 Mon Sep 17 00:00:00 2001 From: Stoycho Kyosev Date: Sun, 22 Dec 2024 13:19:05 -0500 Subject: Add seminar 10 and 11 --- Seminar11/find-cycle.cpp | 54 ++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 54 insertions(+) create mode 100644 Seminar11/find-cycle.cpp (limited to 'Seminar11/find-cycle.cpp') 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 +#include +#include + +using graph = std::vector>; + +enum class color : char +{ + white, + gray, + black +}; + +bool has_cycle_cc(const graph& g, int vertex, std::vector& 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 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 -- cgit v1.3.1-26-gb76a