From 00cd4d0b3541c1026a4c0f8d66d953690299178a Mon Sep 17 00:00:00 2001 From: Stoycho Kyosev Date: Fri, 10 Jan 2025 07:51:36 -0500 Subject: Add code for sem12 --- Seminar12/src/connected-components/count-cc.cpp | 51 +++++++++++++++++++++++++ 1 file changed, 51 insertions(+) create mode 100644 Seminar12/src/connected-components/count-cc.cpp (limited to 'Seminar12/src/connected-components/count-cc.cpp') diff --git a/Seminar12/src/connected-components/count-cc.cpp b/Seminar12/src/connected-components/count-cc.cpp new file mode 100644 index 0000000..4e2e84c --- /dev/null +++ b/Seminar12/src/connected-components/count-cc.cpp @@ -0,0 +1,51 @@ +#include "../graph_impl/graph/graph.h" +#include + +void dfs_visit(const graph& g, graph::vertex_t from, std::vector& visited) +{ + visited[from] = true; + + const auto& adjacent = g.adjacent(from); + + for(const auto& vertex : adjacent) + { + if(!visited[vertex]) + { + dfs_visit(g, vertex, visited); + } + } +} + +size_t count_cc(const graph& g) +{ + std::vector visited(g.vertex_count(), false); + size_t cnt = 0; + + for (int i = 0; i < g.vertex_count(); i++) + { + if(!visited[i]) + { + ++cnt; + dfs_visit(g, i, visited); + } + } + + return cnt; +} + +int main() +{ + graph g(6, false); + + g.add_edge(0, 1); + g.add_edge(0, 2); + g.add_edge(2, 3); + g.add_edge(1, 4); + g.add_edge(3, 5); + g.add_edge(4, 5); + g.add_edge(2, 5); + + g.add_vertex(); + + std::cout << count_cc(g); +} \ No newline at end of file -- cgit v1.3.1-23-gd82d