Sortowanie grafu

0

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;
}
0

Wystarczy że znajdziesz w skierowanym grafie ścieżkę o długości N-1.
Użyj tylko jedna mapa: unordered_map<string,unordered_set<string>> nei;
Nie sądzę aby potrzebowałeś wizyt no chyba że mogą być zapętlenia czy a<b, b<c, c<a.
Proponuje: https://pl.wikipedia.org/wiki/Algorytm_Floyda-Warshalla

1 użytkowników online, w tym zalogowanych: 0, gości: 1