Zadanie i kod do analizy/poprawy
Ostatnio zmodyfikowano 2019-02-22 14:49
Mamcia Temat założony przez niniejszego użytkownika |
Zadanie i kod do analizy/poprawy » 2019-02-22 09:25:42 Witam serdecznie, mam takie zadanie: http://solve.edu.pl/contests/download_desc/2011Dany jest graf nieskierowany. Sprawdź jego spójność. W pierwszej linii wejścia dana jest liczba zestawów danych. Każdy zestaw składa się z liczb N i M, które oznaczają liczbę wierzchołków oraz krawędzi grafu. Następnie danych jest M linii, a w każdej z nich liczby A,B, które oznaczają, że istnieje krawędź między wierzchołkami A oraz B. Dla każdego testu należy wypisać TAK, je˙zeli graf jest spójny lub NIE w przeciwnym wypadku. Mam napisany taki kod, niestety nie działa poprawnie. Może ktoś widzi błąd i pomoże poprawić? Ten przechodzi dwa testy z pięciu: #include <bits/stdc++.h>
using namespace std;
vector < int > graf[ 1000001 ];
bool odw[ 1000005 ];
int tops2 = 0;
bool cohesion[ 1000005 ];
void DFS( int v )
{
odw[ v ] = true;
tops2++;
for( int i = 0; i < graf[ v ].size(); i++ )
{
if( !odw[ graf[ v ][ i ] ] )
{
DFS( graf[ v ][ i ] );
}
}
}
int main()
{
ios_base::sync_with_stdio( false );
cin.tie( 0 );
cout.tie( 0 );
int zestawy, tops, edges;
cin >> zestawy;
for( int i = 0; i < zestawy; ++i ) {
tops2 = 0;
cin >> tops >> edges;
for( int j = 0; j < edges; j++ )
{
int a, b;
cin >> a >> b;
graf[ a ].push_back( b );
graf[ b ].push_back( a );
}
DFS( 1 );
if( tops2 == tops ) {
cohesion[ i ] = true;
}
}
for( int i = 0; i < zestawy; ++i ) {
if( cohesion[ i ] ) cout << "TAK\n";
else cout << "NIE\n";
}
return 0;
} Prawdopodobnie nie czyści graf po teście ale nie wiem jak to zrobić dokładnie i czy miejsce, które sugeruję w kodzie jest dobre? Jak dodam: for( int i = 1; i <= tops; i++ )
graf[ i ].clear();
to mi się wysypuje i mam: Segmentation fault :-( |
|
pekfos |
» 2019-02-22 13:09:34 A nie przechodzi testu, bo..? Zła odpowiedź? Błąd wykonania? Twój rekurencyjny DFS nie jest właściwym podejściem dla tak potencjalnie dużych danych. Dla grafu który jest N-elementową ścieżką dla maksymalnego dozwolonego w zadaniu N, twój program się pewnie wysypie. Koniecznie zapoznaj się też z Mam problem z zadaniem ze SPOJa. |
|
Mamcia Temat założony przez niniejszego użytkownika |
» 2019-02-22 13:16:08 Przechodzi dwa testy z pięciu, na trzecim teście mam błędną odpowiedź.
10^6 to nie jest przecież jakaś wielka liczba.
|
|
pekfos |
» 2019-02-22 13:20:18 | 10^6 to nie jest przecież jakaś wielka liczba. |
Zakład? int main()
{
for( int i = 1; i < 1000000; ++i )
graf[ i ].push_back( i + 1 );
DFS( 1 );
return 0;
} |
|
Mamcia Temat założony przez niniejszego użytkownika |
» 2019-02-22 13:25:22 To co powinienem zrobić ? |
|
pekfos |
» 2019-02-22 13:28:07 Nie używać rekurencji. |
|
Mamcia Temat założony przez niniejszego użytkownika |
» 2019-02-22 13:48:37 cholercia czyli iteracja? nie wiem czy ogarnę :-)
Może ktoś jest w stanie pomóc w zmianie rekurencji w moim kodzie na iterację ? |
|
pekfos |
» 2019-02-22 13:57:50 W takim prostym algorytmie to trywialne. Zamiast wywoływać funkcję rekurencyjnie, zapisuj argument do jakiegoś kontenera. Algorytm zaczyna ze startową wartością w kontenerze i wykonuje się tak długo, aż kontener będzie pusty. Dla BFS kontener powinien się zachowywać jak kolejka, a dla DFS jak stos. |
|
| « 1 » 2 |