From a8405a4a88b2494c742457f853411b6fe80e2f9b Mon Sep 17 00:00:00 2001 From: Stoycho Kyosev Date: Tue, 17 Jan 2023 15:12:45 +0200 Subject: Add Sem13 --- Seminar13/README.md | 20 +++++++++++++ Seminar13/task01.cpp | 85 ++++++++++++++++++++++++++++++++++++++++++++++++++++ Seminar13/task02.cpp | 41 +++++++++++++++++++++++++ 3 files changed, 146 insertions(+) create mode 100644 Seminar13/README.md create mode 100644 Seminar13/task01.cpp create mode 100644 Seminar13/task02.cpp 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 +#include +#include + +bool hasCycleRec(const std::vector>& graph, int start, std::vector& 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>& graph) { + std::vector 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>& prerequisites) { + std::vector> graph(numCourses); + + for (const auto& edgePair : prerequisites) + graph[edgePair.first].push_back(edgePair.second); + + // Степен на вход на върховете + std::vector inDegree(numCourses, 0); + + for(int i = 0; i < numCourses; i++) { + for(const auto& vertex : graph[i]) { + inDegree[vertex]++; + } + } + + std::queue 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 +#include +#include +#include + +bool canRead(const std::multimap& 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 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 visited; + std::string word = "adaz"; + + std::cout << canRead(graph, word, 0); +} \ No newline at end of file -- cgit v1.3.1-26-gb76a