zadanie z grafów - topo sort

Question

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

Answer 1

Trochę podejrzane jesli N <= 300. To powinno się wykonywać w najgorszym wypadku o rząd mniej niż 1s. Możesz spróbować zamienić string na inta, wtedy za każdym razem jak korzystasz z unordered map to nie trzeba będzie hashować tych stringów

Comments

przechodze po kopii mojego stosu i sprawdzam, czy kazdy nastepnik w stosie jest sasiadem aktualnie sprawdzanego w stosie. gdzie tu jest blad w algorytmie? a moze po prostu moja implementacja jest zla...

---

Co jak jest cykl długości N?

---

dodałem warunek sprawdzający takie zdarzenie i nadal wypluwa błąd

po wyjściu z while:

if (find(nei[_this].begin(), nei[_this].end(), sta.top()) != nei[_this].end())
	con = 0;

---

Jak tak teraz myśle to chyba jednak trzeba sprawdzić czy istnieje jakikolwiek cykl.

---

Whistleroosh, dalej nic.

kod na moje oko jest w pełni zoptymalizowany, ze szczegółami.

algorytm jest wyczulony na wszelakie cykle w grafie, jak również na sytuacje takiego typu: a > b oraz c > b.

wyniki: https://imgur.com/a/zR3r3wp

#include <bits/stdc++.h>

using namespace std;

unordered_map <string, vector <string>> nei;
unordered_map <string, int> vis;
stack <string> sta, cop;
bool con = 1;
//con z ang. condition - warunek, z gory przyjmuje, 
//ze da sie posortowac osoby, jesli wyklucze taka
//mozliwosc, wtedy ustawie con na wartosc 0

void topoSort(string str); //no comment

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int n;
	cin >> n;

	string a, b;
	while (n --) {
		cin >> a >> b;
		nei[a].push_back(b); //zapisanie grafu
	}

	for (auto i = nei.begin(); i != nei.end(); i ++) {
		if (!vis[i -> first])
			topoSort(i -> first);
	}

	if (!con) //jezeli wystapil cykl
		cout << "NIE";
	else {
		cop = sta; //skopiowanie staku
		a = cop.top(); //
		cop.pop();

		while (!cop.empty()) {
			//przejscie po stosie i sprawdzenie czy istnieje jedna
			//sciezka laczaca wszystkie wierzcholki grafu
			if (find(nei[a].begin(), nei[a].end(), cop.top()) == nei[a].end())
				con = 0;
			a = cop.top();
			cop.pop();
		}

		if (!con) //jezeli wystapila np. taka sytuacja: a > b oraz c > b
			cout << "NIE";
		else {
			while (!sta.empty()) {
				cout << sta.top() << '\n';
				sta.pop();
			}
		}
	}
}

void topoSort(string str) {
	vis[str] = 2; //aktualnie sprawdzany = 2

	for (string _str : nei[str]) {
		//jezeli wystapil cykl
		if (vis[_str] == 2) 
			con = 0;

		//dalsze 'zaglebienie' rekurencji
		if (!vis[_str]) 
			topoSort(_str);
	}

	sta.push(str);
	vis[str] = 1; //aktualnie niesprawdzany, ale sprawdzony = 1
}