• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

zadanie z grafów - topo sort

Object Storage Arubacloud
0 głosów
600 wizyt
pytanie zadane 14 stycznia 2023 w C i C++ przez polandonion Mądrala (7,210 p.)
edycja 15 stycznia 2023 przez polandonion

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

1 odpowiedź

0 głosów
odpowiedź 15 stycznia 2023 przez Whistleroosh Maniak (56,980 p.)
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
komentarz 15 stycznia 2023 przez polandonion Mądrala (7,210 p.)
edycja 15 stycznia 2023 przez polandonion
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...
komentarz 15 stycznia 2023 przez Whistleroosh Maniak (56,980 p.)
Co jak jest cykl długości N?
komentarz 15 stycznia 2023 przez polandonion Mądrala (7,210 p.)
edycja 15 stycznia 2023 przez polandonion

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;
komentarz 15 stycznia 2023 przez Whistleroosh Maniak (56,980 p.)
Jak tak teraz myśle to chyba jednak trzeba sprawdzić czy istnieje jakikolwiek cykl.
komentarz 16 stycznia 2023 przez polandonion Mądrala (7,210 p.)

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
}

 

Podobne pytania

0 głosów
0 odpowiedzi 287 wizyt
pytanie zadane 7 stycznia 2023 w C i C++ przez polandonion Mądrala (7,210 p.)
0 głosów
1 odpowiedź 255 wizyt
pytanie zadane 10 lutego 2021 w C i C++ przez KumberTwo Dyskutant (8,270 p.)
0 głosów
1 odpowiedź 98 wizyt
pytanie zadane 28 stycznia 2022 w C i C++ przez Mikusia^-^22 Nowicjusz (120 p.)

92,759 zapytań

141,680 odpowiedzi

320,444 komentarzy

62,102 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...