diff options
Cleanup
3 files changed, 0 insertions, 146 deletions
| -rw-r--r-- | Seminar13/README.md | 20 | ||||
| -rw-r--r-- | Seminar13/task01.cpp | 85 | ||||
| -rw-r--r-- | Seminar13/task02.cpp | 41 |
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 |
