diff options
Add seminar 10 and 11
1 files changed, 54 insertions, 0 deletions
| -rw-r--r-- | Seminar11/find-cycle.cpp | 54 |
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 |
