Добавил шестую задачу в графах

2 files changed, 109 insertions, 2 deletions

diff --git a/graphs/Makefile b/graphs/Makefile
index b61c5fb..8810093 100644
--- a/graphs/Makefile
+++ b/graphs/Makefile
@@ -41,8 +41,12 @@ test5: task5
 task6:
 	$(COMPILE) -o task.out task6.cpp
 test6: task6
-	@printf "" | ./task.out
-	@printf "Answer: \n"
+	@printf "5\n3\n1 3\n2 3\n4 5\n3" | ./task.out
+	@printf "Answer: 1, 2\n"
+	@printf "5\n3\n1 3\n2 3\n4 3\n3" | ./task.out
+	@printf "Answer: 1, 2, 4\n"
+	@printf "5\n3\n1 3\n2 3\n4 3\n5" | ./task.out
+	@printf "Answer: none\n"
 
 clean:
 	rm -f task.out *.zip
diff --git a/graphs/task6.cpp b/graphs/task6.cpp
new file mode 100644
index 0000000..3c8f8b9
--- /dev/null
+++ b/graphs/task6.cpp
@@ -0,0 +1,103 @@
+#include<iostream>
+#include<vector>
+#include<algorithm>
+
+using namespace std;
+
+typedef vector<vector<int>> graph;
+
+void print(graph g)
+{
+    for (int i = 0; i < int(g.size()); ++i)
+    {
+        cout << i + 1 << ": ";
+        for (int j = 0; j < int(g[i].size()) - 1; ++j)
+            cout << g[i][j] + 1 << ", ";
+
+        if (g[i].size() > 0)
+            cout << g[i].back() + 1;
+        else
+            cout << "нет смежных вершин";
+
+        cout << ";" << endl;
+    }
+}
+
+void dfs(int x, graph g, vector<int> *path, vector<int> *used)
+{
+    (*used)[x] = 1;
+    path->push_back(x);
+    for (int i = 0; i < int(g[x].size()); ++i)
+    {
+        int node = g[x][i];
+        if ((*used)[node] == 0)
+            dfs(node, g, path, used);
+    }
+
+}
+
+void dfs(int x, graph g, vector<int> *path)
+{
+    int n = int(g.size());
+    vector<int> used(n);
+    dfs(x, g, path, &used);
+}
+
+
+int main()
+{
+    cout << "Введите количество вершин: ";
+    int n;
+    cin >> n;
+
+    cout << "Введите количество рёбер: ";
+    int k;
+    cin >> k;
+
+    graph g(n);
+    
+    cout << "o----------------------o" << endl;
+    cout << "| Нумерация вершин с 1 |" << endl;
+    cout << "o----------------------o" << endl;
+
+    cout << "Введите рёбра (ориентированные):" << endl;
+    for (int i = 0; i < k; ++i)
+    {
+        int a, b;
+        cin >> a >> b;
+        a--;
+        b--;
+        g[a].push_back(b);
+    }
+
+    cout << "Введённый граф:" << endl;
+    print(g);
+
+    cout << "Введите анализируемую вершину: ";
+    int a;
+    cin >> a;
+    a--;
+
+    vector<int> nodes;
+    for (int i = 0; i < n; ++i)
+    {
+        if (i == a) continue;
+
+        vector<int> path;
+        dfs(i, g, &path);
+        if (find(path.begin(), path.end(), a) != path.end())
+            nodes.push_back(i);
+    }
+
+    if (nodes.size() == 0)
+        cout << "В вершину " << a + 1 << " нет путей из других вершин" << endl;
+    else
+    {
+        cout << "В вершину " << a + 1 << " есть пути из вершин: ";
+        for (int i = 0; i < int(nodes.size()) - 1; ++i)
+            cout << nodes[i] + 1 << ", ";
+        cout << nodes.back() + 1 << endl;
+    }
+
+    return 0;
+}