Задача: Рекурсия
Решение
ссылка на ideone, засчитанное решение на e-olimp
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
#include<iostream> #include<vector> #include<set> #include<map> #include<string> using namespace std; map<string,set<string>> G; map<string,bool> used; map<string,bool> rec; vector<string> V; void dfs(string cur, string aim){ if(used[cur] || rec[aim]) return; used[cur] = 1; for(auto i = G[cur].begin(); i != G[cur].end(); i++){ if(*i != aim){ dfs(*i,aim); }else{ rec[aim] = 1; return; } } } int main(){ //input int n; cin >> n; for(int i = 0; i < n; i++){ string curVert; cin >> curVert; V.push_back(curVert); int m; cin >> m; while(m--){ string inp; cin >> inp; G[curVert].insert(inp); } if(i != n-1){ string stars; cin >> stars; } } //work for(auto i : V){ dfs(i, i); used.clear(); } for(auto i : V){ cout << i << (rec[i] ? ": YES" : ": NO") << endl; } return 0; } |
Идея решения
Можно заметить, что каждая процедура — это вершина ориентированного графа. Чтобы узнать, является ли процедура потенциально рекурсивной, нужно было запустить из неё поиск в глубину и узнать, сможем ли мы прийти к ней вновь.
Было решено использовать
map<string,set<string>> как структуру для описания графа: каждая вершина — это строка и у каждой вершины есть множество вершин (строк), смежных с ней.
А еще задача имеет классификацию — поиск в глубину, что как бы намекает.
Добавьте, пожалуйста, метки
Метки добавлены
Принято. Молодец!