Add code for sem12

1 files changed, 51 insertions, 0 deletions

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 <iostream>
+
+void dfs_visit(const graph& g, graph::vertex_t from, std::vector<bool>& 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<bool> 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