Website Summary Files Commits Branches @commit @diff @stats
path: root / Seminar13
diff options
context:
space:
mode:
Commit7eee5a78005a9a569186d2c8b4b645a818ab9bf1 (patch)
Author
 Stoycho Kyosev <skyosev@192.168.100.17>
2024-10-06 07:04:44 -0400
Committer
 Stoycho Kyosev <skyosev@192.168.100.17>
2024-10-06 07:04:44 -0400
Files84594e0af29cefa5aae76ace5f8eb81484400e31 /Seminar13
Data-structures-and-algorithms-7eee5a78005a9a569186d2c8b4b645a818ab9bf1.tar
Data-structures-and-algorithms-7eee5a78005a9a569186d2c8b4b645a818ab9bf1.tar.gz
Data-structures-and-algorithms-7eee5a78005a9a569186d2c8b4b645a818ab9bf1.zip
Parent0841635826cb03c0e74cd75ec3c97c4c3b594d8b (diff)
Cleanup
3 files changed, 0 insertions, 146 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
deleted file mode 100644
index 68c03ef..0000000
--- a/Seminar13/README.md
+++ /dev/null
@@ -1,20 +0,0 @@
-# Задачи върху графи
-
-## Задача първа
-Имаме 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
deleted file mode 100644
index ff33136..0000000
--- a/Seminar13/task01.cpp
+++ /dev/null
@@ -1,85 +0,0 @@
-#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
deleted file mode 100644
index 8d47b45..0000000
--- a/Seminar13/task02.cpp
+++ /dev/null
@@ -1,41 +0,0 @@
-#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