Witam, przerabiam zadanka z grafów na szkopule. To, za które się dzisiaj zabrałem nie było łatwe, musiałem pierwszy raz w życiu użyć mapy (więc także się z nią zapoznać na yt i cppreference). Niestety jeden z testów mi nie wchodzi ze względu na czas. Pomoże ktos?
zadanie: link
wyniki: link
#include <iostream>
#include <unordered_map>
#include <stack>
#include <vector>
using namespace std;
unordered_map <string, vector <string>> nei;
unordered_map <string, bool> vis;
stack <string> sta;
bool con;
int _vis;
void topoSort(string str);
void dfs(string str);
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n;
cin >> n;
while (n --) {
string a, b;
cin >> a >> b;
nei[a].push_back(b);
}
for (auto i = nei.begin(); i != nei.end(); i ++) {
if (!vis[i->first])
topoSort(i->first);
}
vis.clear();
dfs(sta.top());
if (!con)
cout << "NIE";
else {
while (!sta.empty()) {
cout << sta.top() << '\n';
sta.pop();
}
}
}
void topoSort(string str) {
vis[str] = 1;
for (string _this : nei[str]) {
if (!vis[_this])
topoSort(_this);
}
sta.push(str);
}
void dfs(string str) {
vis[str] = 1;
_vis ++;
if (_vis == nei.size())
con = 1;
for (string _this : nei[str]) {
if (!vis[_this])
dfs(_this);
}
_vis --;
vis[str] = 0;
}