Wczytywanie grafu

Pojawiły się małe problemy, co do tego jak wczytać graf, no to już tłumaczę ;)

Powiedzmy, że mamy wczytać graf o V wierzchołkach i E krawędziach, no to robimy to tak:

vector <int> G[V];
 
void wczytaj()
{
    for (int i=0; i<E; i++)
    {
        int a, b;
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a); //TYLKO W NIESKIEROWANYM!!
    }
}

Basta ;)

A teraz co to jest??

vector <int> G[V];
vector, to taka "samorosnąca tablica", gdzie trzymamy sobie sąsiadów jakiegoś wierzchołka, np. w G[2] będą się znajdować wszystkie wierzchołki, do których można dotrzeć z wierzchołka 2.
Zamiast "int" w tych nawiasikach można dać dowolny typ, nawet własną strukturkę.
Przydatne funkcje na vectorze:
push_back(zmienna) - wrzuca coś na wektor
clear() - czyści vector
size() - zwraca liczbe zmiennych w vectorze

wczytujemy sobie zmienne a i b, które oznaczają, że między wierzchołkami a i b jest krawędź, jeśli jest skierowana, to do G[a] wrzucamy "b", a jak nieskierowana, to jeszcze do G[b] wrzucimy "a"

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License