Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _USE_MATH_DEFINES
- #include <iostream>
- #include <conio.h>
- #include <string>
- #include <set>
- #include <map>
- #include <algorithm>
- #include <string>
- #include <math.h>
- #include <vector>
- #include <cmath>
- #include <sstream>
- #include <queue>
- using namespace std;
- struct top // структура вершины дерева
- {
- string num; // номер префикса
- string name; // название задачи
- map <string, top*> next; // ссылке на следующие префиксы ниже рангом
- };
- top* Newtop(string num, string name) // создания новой вершины дерева
- {
- top* Top = new top();
- Top->num = num;
- Top->name = name;
- return Top;
- }
- string addtree(queue<string>parag, string name, map <string, top*> coren) /* добавляем в дерево новую тему и узнаем список с ей и её родителями*/
- {
- top* topWhat = new top(); // итоговая вершина данной темы
- top* proms = new top(); // промежуточная вершина дерева
- string d = "";//список с темой и её родителями
- proms = coren[parag.front()];//узнаём ссылку на корневой элемент дерева
- parag.pop();// удаляем этот префикс из очереди
- d += proms->name + ".";// добавляем корневую тему в список
- while (parag.size()!=1) // бежим пока не останется вставляемая тема
- {
- proms = proms->next[parag.front()]; // движемся по дереву к следующему префиксу
- d += proms->name + "."; // добавляем родителей темы в список
- parag.pop();//вновь освобождаем место у кассы)
- }
- topWhat = Newtop(parag.front(), name); // ссылка на вставляемую в дерево тему
- d += name;// добавляем саму тему в список
- proms->next[parag.front()] = topWhat;//добавляем тему в дерево
- return d;//возражающем список
- }
- set<string> finds(map <int, set <string>> exc, string nums, set<string>* proms) /* проверяем не встретились ли нам задачи с одинаковым количеством и названием тем (список с номерами задач и темами к ним, номер задачи, и список со всеми использованными задачами*/
- {
- set<string> num;//номера с одинаковым количеством и названием тем
- set<string> prom;//промежуточный список тем у данной задачи
- num.insert(nums);// добавляем данную задачу в совпадающие
- proms->insert(nums);// добавляем данную задачу в использованные
- prom = exc[atoi(nums.c_str())]; // узнаем список тем с которым надо сравнить
- for (auto i = exc.begin(); i != exc.end(); i++) // проверяем
- {
- if (i->first != atoi(nums.c_str()))//проверка не та ли эта задача с которой сравниваем
- {
- if (prom == i->second) // проверяем совпадает ли список тем
- {
- num.insert(to_string(i->first)); // если да, то впихиваем этот номер задачи в совпадающие и в использованные
- proms->insert(to_string(i->first));
- }
- }
- }
- return num;
- }
- int main()
- {
- map <string, top*> coren; // дерево префиксов
- map <int, set <string>> exc; // номера задач с списком из тем и их родителей
- string prom;//промежуточная строка префикса
- string name;// название темы
- string promi="10";// промежуточный номер задач
- bool d = true;
- cin >> prom;
- while (d)
- {
- string toprom="";//список из этой темы и её родителей
- queue<string>parag;
- d = false;
- int i=0;
- int last=0;
- while (i != prom.size()) // создаем очередь префиксов, чтобы было проще находить предка
- {
- if (prom[i] == '.')//следовательно число закончилось, ведь оно может быть двузначным
- {
- parag.push(prom.substr(last, i - last));
- i++;
- last = i;
- }
- else
- i++;
- }
- getline(cin, name); // ввод темы
- name = name.substr(1, name.size() - 1);//так как там пробел есть
- if (parag.size() == 1) // если это корневой префикс
- {
- top* t = new top();
- t = Newtop(parag.front(), name);
- coren[parag.front()] = t;
- toprom = t->name;
- }
- else
- {
- toprom = addtree(parag, name, coren);//иначе идём до него и заодно пишем путь его и родителей
- }
- while (cin >> promi)//ввод номеров задач
- {
- if (promi[1] == '.' || promi[2] == '.')//если пошёл ввод следующей темы
- {
- prom = promi;
- d = true;
- break;
- }
- else
- {
- exc[atoi(promi.c_str())].insert(toprom); // ввод в номер задачи список из этой темы и её родителей
- }
- }
- toprom = "";
- }
- set<string>* proms=new set<string>();//использованные задачи
- set < string> promd;
- for (auto i = exc.begin(); i != exc.end(); i++) // вывод
- {
- string num;
- num = to_string(i->first); // номер текущей задачи
- if (proms->find(to_string(i->first)) == proms->end()) // проверка не использовали ли мы эту задачу ранее
- {
- promd = finds(exc, num, proms);//проверка есть ли ещё задачи с такими же темами, как данная
- for (auto j = promd.begin(); j != promd.end(); j++)//вывод номеров задач
- {
- if (++j != promd.end())
- {
- j--;
- cout << *j << ", ";
- }
- else
- {
- j--;
- cout << *j << " : ";
- }
- }
- for (auto j = i->second.begin(); j != i->second.end(); j++) //вывод тем
- {
- if (++j != i->second.end())
- {
- j--;
- cout << *j << ", ";
- }
- else
- {
- j--;
- cout << *j << endl;
- }
- }
- }
- }
- _getch();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment