Website Summary Files Commits Branches @commit @diff @stats
diff options
context:
space:
mode:
Commita8405a4a88b2494c742457f853411b6fe80e2f9b (patch)
Author
 Stoycho Kyosev <stoycho.kk@gmail.com>
2023-01-17 15:12:45 +0200
Committer
 Stoycho Kyosev <stoycho.kk@gmail.com>
2023-01-17 15:12:45 +0200
Files1cd07e4e70e6af74ef4ba6cd757a4f777d71ff2e
Data-structures-and-algorithms-a8405a4a88b2494c742457f853411b6fe80e2f9b.tar
Data-structures-and-algorithms-a8405a4a88b2494c742457f853411b6fe80e2f9b.tar.gz
Data-structures-and-algorithms-a8405a4a88b2494c742457f853411b6fe80e2f9b.zip
Parent27c4ede68074617b373d8e990932f3d22d34f8ab (diff)
Add Sem13
3 files changed, 146 insertions, 0 deletions
-rw-r--r--Seminar13/README.md20
-rw-r--r--Seminar13/task01.cpp85
-rw-r--r--Seminar13/task02.cpp41
diff --git a/Seminar13/README.md b/Seminar13/README.md
new file mode 100644
index 0000000..68c03ef
--- /dev/null
+++ b/Seminar13/README.md
@@ -0,0 +1,20 @@
+# Задачи върху графи
+
+## Задача първа
+Имаме n курса, които трябва да вземем, означени с числа от 0 до n - 1. Като вход получаваме вектор от двойки (i, j) и брой на курсовете. Всяка двойка във вектора означава, че курсът с етикет i трябва да се вземе преди курсът с етикет j. Да се провери дали е възможно курсовете да се вземат.
+
+``` Пример
+Вход: [[0, 1]], 2
+
+Изход: Да, първо вземаме курс 0 а после курс 1.
+
+Вход: [[0, 1], [1, 0]], 2
+
+Изход: Не.
+```
+
+## Задача втора
+Даден е ориентиран граф от уникални символи g. Да се напише функция, която приема графа и дума с произволна дължина и проверява дали думата може да се получи чрез конкатенирането на последователни различни върхове в графа.
+
+## Задача трета
+Да се напише функция, която намира сумата на най - големите елементи на отделните свързани компоненти в (неориентиран) граф. \ No newline at end of file
diff --git a/Seminar13/task01.cpp b/Seminar13/task01.cpp
new file mode 100644
index 0000000..ff33136
--- /dev/null
+++ b/Seminar13/task01.cpp
@@ -0,0 +1,85 @@
+#include<vector>
+#include<queue>
+#include<iostream>
+
+bool hasCycleRec(const std::vector<std::vector<int>>& graph, int start, std::vector<bool>& visited) {
+ visited[start] = true;
+
+ for (const auto& vertex : graph[start]) {
+ if (visited[vertex])
+ return true;
+
+ if (hasCycleRec(graph, vertex, visited))
+ return true;
+ }
+
+ visited[start] = false;
+
+ return false;
+}
+
+bool hasCycle(const std::vector<std::vector<int>>& graph) {
+ std::vector<bool> visited(graph.size(), false);
+
+ for (int i = 0; i < graph.size(); i++) {
+ if (!visited[i] && hasCycleRec(graph, i, visited)) {
+ return true;
+ }
+ }
+
+ return false;
+}
+
+// Използваме алгоритъм на Kahn за топологично сортиране
+bool canFinish(int numCourses, std::vector<std::pair<int, int>>& prerequisites) {
+ std::vector<std::vector<int>> graph(numCourses);
+
+ for (const auto& edgePair : prerequisites)
+ graph[edgePair.first].push_back(edgePair.second);
+
+ // Степен на вход на върховете
+ std::vector<int> inDegree(numCourses, 0);
+
+ for(int i = 0; i < numCourses; i++) {
+ for(const auto& vertex : graph[i]) {
+ inDegree[vertex]++;
+ }
+ }
+
+ std::queue<int> q;
+
+ // Добавяме тези със степен нула. Те ще са първи в топологичната сортировка.
+ for(int i = 0; i < numCourses; i++) {
+ if(inDegree[i] == 0) {
+ q.push(i);
+ }
+ }
+
+ // Правим подобно на BFS търсене.
+ // След като "изтрием" върховете със степен на вход 0 има други върхове
+ // със степен на вход 0. Те са следващите в топологичната сортировка.
+ while(!q.empty()) {
+ int currentNode = q.front();
+ q.pop();
+
+ for(const auto& n : graph[currentNode]) {
+ inDegree[n]--;
+
+ if(inDegree[n] == 0)
+ q.push(n);
+ }
+ }
+
+ // Ако след това обхождане има връх със степен
+ // различна от 0, то в графа има цикъл.
+ for(const auto& n : inDegree) {
+ if(n != 0)
+ return false;
+ }
+
+ return true;
+}
+
+int main() {
+
+} \ No newline at end of file
diff --git a/Seminar13/task02.cpp b/Seminar13/task02.cpp
new file mode 100644
index 0000000..8d47b45
--- /dev/null
+++ b/Seminar13/task02.cpp
@@ -0,0 +1,41 @@
+#include<iostream>
+#include<string>
+#include<map>
+#include<vector>
+
+bool canRead(const std::multimap<char, char>& graph, const std::string& word, size_t at) {
+ if(at == word.length() - 1)
+ return true;
+
+ auto successors = graph.find(word[at]); // Може ли да си спестим това търсене?
+
+ if(successors == graph.end())
+ return false;
+
+ while(successors != graph.end() && (*successors).first == word[at]) {
+ if((*successors).second == word[at + 1]) {
+ return canRead(graph, word, at + 1);
+ }
+
+ ++successors;
+ }
+
+ return false;
+}
+
+int main() {
+ std::multimap<char, char> graph;
+
+ graph.insert({'a', 'c'});
+ graph.insert({'a', 'd'});
+ graph.insert({'c', 'b'});
+ graph.insert({'b', 'd'});
+ graph.insert({'d', 'k'});
+ graph.insert({'d', 'c'});
+ graph.insert({'d', 'a'});
+
+ std::map<char, bool> visited;
+ std::string word = "adaz";
+
+ std::cout << canRead(graph, word, 0);
+} \ No newline at end of file