Implementacja grafu - segmentation fault

[pawegio]

Kod: Zaznacz cały

#include <cstdio>
#include <vector>

using namespace std;

int n,m,a,b;
vector< vector<int> > g;

int main() {
	scanf("%d %d",&n,&m);
	for(int i=0;i<n;i++) {		
		scanf("%d %d",&a,&b);
		g[a].push_back(b);
		g[b].push_back(a);
	}
	return 0;
}

Chyba coś przeoczyłem i nie widzę błędu, ale wyrzuca Segmentation fault

[beluosus]

Jeszcze żebyś powiedział co ten kod ma robić... wiesz, mogę poprawić żeby nie było "segfa" ale skąd mam wiedzieć, że będzie robił to co Ty chcesz żeby robił. Na początek to widzę jedynie niepotrzebną zmienną "m". Później do nieistniejących elementów chcesz coś wrzucać... Nie jestem pewien czy wiesz jak działają wektory. Załączę taki przykładzik, może się przyda.

Kod: Zaznacz cały

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    vector <int> x;
    vector <int> y;
    vector <vector <int> > zz;

    x.push_back(111);
    x.push_back(222);
    x.push_back(333);
    zz.push_back(x);

    y.push_back(444);
    y.push_back(555);
    y.push_back(666);
    zz.push_back(y);

    cout << zz[0][0] << endl
         << zz[0][1] << endl
         << zz[0][2] << endl
         << endl
         << zz[1][0] << endl
         << zz[1][1] << endl
         << zz[1][2] << endl;

    return 0;
}

[pawegio]

ok, dzięki....
rzeczywiście nie za bardzo się wyraziłem o co chodzi.... Chciałem zaimplementować graf nieskierowany... m to liczba par wierzchołków do wczytania, a n to liczba wierzchołków. Normalnie użyłbym tablicy dwuwymiarowej i by było:

Kod: Zaznacz cały

g[a][b]=1; g[b][a]=1;

ale ze względu na liczbę danych stwierdziłem, że skorzystam z STL'a. Może jest jakiś lepszy sposób na implementację grafu?

[luzakwielki]

@pawegio: musisz zaalokować rozmiar wektorów (np. 10 wektorów po 5 elementów):

Kod: Zaznacz cały

vector< vector<int> > g(10,vector< int > (5));

Teraz po prostu chcesz pisać tam gdzie nie możesz (nie zaalokowałeś pamięci) i wywala problem.

ok, dzięki....
rzeczywiście nie za bardzo się wyraziłem o co chodzi.... Chciałem zaimplementować graf nieskierowany... m to liczba par wierzchołków do wczytania, a n to liczba wierzchołków. Normalnie użyłbym tablicy dwuwymiarowej i by było:

Kod: Zaznacz cały

g[a][b]=1; g[b][a]=1;

ale ze względu na liczbę danych stwierdziłem, że skorzystam z STL'a. Może jest jakiś lepszy sposób na implementację grafu?

Użycie tablicy i takiego wektora to słabe rozwiązanie (chyba, że jest to graf bardzo gęsty). Ogólnie nawet jak jest gęsty i tak będziesz ją reprezentował (jako macierz) to w grafie nieskierowanym nie potrzeba Ci całej tablicy a tylko macierz trójkątną (prawie 2x mniej użytej pamięci).
Do grafów rzadkich lepiej użyj własnej struktury, gdzie każdy wierzchołek jest reprezentowany przez strukturę, a ścieżki jako lista wskaźników (lub lista struktur (wskaźnik+waga+kolor+...)) w tej strukturze.