Efektywne sprawdzenie dwudzielności i spójności grafu

Witam, mam do napisania kod sprawdzający dwudzielność i ilość składowych spójności grafu. I tak właściwie to... zrobiłem to, ale mój kod jest bardzo, bardzo nieefektywny dla dużych grafów (niestety, nie mogę określić jak dużych, sprawdza mi to kochany spoj :)) Mogę liczyć na jakieś wskazówki, jak możnaby zrobić to lepiej? (nie liczę na gotowe rozwiązanie, tylko jakiś pomysł, na który wpaść nie mogę). O spowalnianie kodu podejrzewam rekurencję, ale nie potrafię sobie poradzić bez niej. :(

Starałem się obkomentować kod jak najlepiej, ale jeśli coś jest niejasne to proszę pytać.

Oto mój dotychczasowy kod (troszkę ucięty dla czytelności, ale kluczowe elementy pozostają te same)

#include <cstdlib>
#include <iostream>
#include <vector>
#include <list>

using namespace std;

class Node {
  int nr;

  public :
    Node(int nr) {
      this->nr = nr;
    }
    int & GetNr() {
      return nr;
    }
};

// funkcja sprawdza dwudzielność grafu, parametrami są graf w postaci wektora list
// aktualnie przetwarzany wierzchołek (powinno się zaczynać od 0), wektor stanu wierzchołków,
// oraz nr. zbioru do którego ma należeć wierzchołek (kolor wierzchołka, 1 lub -1)
bool CheckBipartite(vector <list<Node> > graf, int wierzcholek, vector <int> &wierzcholki, int zbior) {
  bool isBipartite = false;

    for (list<Node>::iterator current = graf[wierzcholek].begin(); current != graf[wierzcholek].end();) {
      int currentNr = wierzcholki[current->GetNr()];
      if (currentNr == -zbior) continue; //jesli prawidlowo pokolorowany, pomiń
      else if (currentNr == zbior) { //jesli źle, graf nie jest dwudzielny
        return isBipartite;
      } else if (currentNr == 0) { // jeśli niepokolorowany, nadaj przeciwny kolor i wywołaj funkcję dla sąsiadów
          wierzcholki[current->GetNr()] = -zbior;
          //sprawdz czy sąsiedzi nie zaalarmowali, że graf nie jest dwudzielny
          if (!CheckBipartite(graf, current->GetNr(), wierzcholki, -zbior)) return isBipartite;
        }
      ++current;
    }
    isBipartite = true;
    return isBipartite;
}

//BFS, "odwiedza" wierzchołki
void SetVertexAsVisited(vector <list<Node> > graf, int wierzcholek, vector <int> &wierzcholki) {
  if (wierzcholki[wierzcholek] == 0) {
    wierzcholki[wierzcholek] = 1;
    for (list<Node>::iterator current = graf[wierzcholek].begin(); current != graf[wierzcholek].end();) {
      SetVertexAsVisited(graf, current->GetNr(), wierzcholki);
      ++current;
    }
  }
}

//funkcja obliczająca ilość składowych spójności
int HowManyCComponents(vector <list<Node> > graf, vector <int> &wierzcholki) {
  int ConnectedComponents = 1;
  SetVertexAsVisited(graf, 0, wierzcholki); //najpierw dla 1 wierzcholka
  for (int i=0; i<wierzcholki.size(); ++i) { //maksymalna ilosc skladowych to size()
    if (wierzcholki[i] == 0) { // jesli w tablicy sa jakieś 0
      ++ConnectedComponents; // znaczy że nie można było dojść do któregos wierzcholka
      SetVertexAsVisited(graf, i, wierzcholki); // wniosek, kolejna składowa spojności
    }
  }
  return ConnectedComponents;
}

int main(int argc, char** argv) {

  int wierzcholki, krawedzie;
  int para1, para2;
  bool isError = false;

  cin >> wierzcholki >> krawedzie;
  //wczytujemy graf nieskierowany do wektora list
  vector <list<Node> > graf(wierzcholki);
  //odczytujemy krawedzie w grafie
  for (int i=0; i < krawedzie; ++i) {
    // wczytaj wierzcholki do polaczenia ze sobą
    cin >> para1 >> para2;
    --para1; //wierzcholki numerowane od 1 do size()!
    --para2; //każda operacja wyswietlenia wierzchołków na ekranie
             //musi byc poprzedzona dodaniem jedynki
    // czy podano wierzcholki ktore nie istnieja w grafie?
    if (para1 > wierzcholki || para2 > wierzcholki) {
      isError = true;
      break;
    }
    Node a(para2);
    Node b(para1);
    //wpisz wierzcholki do odpowiednich list
    graf[para1].push_back(a);
    graf[para2].push_back(b);
  }
  cout << endl;
  if (isError) return (EXIT_FAILURE);

  vector <int> vwierzcholki(wierzcholki); //przetrzymuje stan wierzcholkow
  //do sprawdzenia spójności grafu
  cout << HowManyCComponents(graf, vwierzcholki) << " ";
  
  //zerowanie wektora stanów
  vwierzcholki.assign(wierzcholki, 0);

  // do sprawdzenia dwudzielności grafu
  vwierzcholki[0] = 1; //nr zbioru pierwszego wierzcholka
  
  if (CheckBipartite(graf, 0, vwierzcholki, 1)) cout << "T";
  else cout << "N\n";
  return (EXIT_SUCCESS);
}

Pokaż to zadanie z ciekawości :)
Ogólnie reprezentacja grafu w postaci listy jest niedobra.
Lepiej zrobić tablicę vectorów, jest kilkukrotnie szybsza.
Jeżeli dużo danych wczytujesz to warto użyć na początku przed wczytaniem:

ios_base::sync_with_stdio(0);

Zadanie brzmi właśnie, zbuduj i wczytaj graf, sprawdz ile ma składowych spójności, czy jest dwudzielny i (no dobra, ale to mi działa doskonale) maksymalny i minimalny stopnień grafu. Nic ciekawego. Nuda wręcz. Kolejne zadanko, które mam do zrobienia na grafie jest ciekawsze. :P (ale to może później)

Co do reprezentacji, ponoć reprezentacja grafu na wektorze list jest wskazana gdy potrzebne jest szybkie określenie sąsiadów danego wierzchołka, co jest mi właśnie potrzebne. Mówisz, że macierz sąsiedztwa byłaby lepsza?

No i wątpię, żebym przekraczał ten czas z powodu wczytywania danych, raczej przez ich przetwarzanie, ale wskazówkę zastosuje. :)

Nie mówiłem o macierzy sąsiedztw. Mówiłem o reprezentacji przez listę sąsiedztw ale w inny sposób - nie na liście tylko na vectorach.
Chodziło mi o link do zadania to bym sobie też zrobił :-)

Mówisz o liście sąsiedztwa bez wykorzystania list? :D Brzmi ciekawie. ;) No cóż, spróbuję i dam znać co z tego wyszło.

Contest jest zamknięty, dlatego tak właśnie napisałem, przykro mi :(

Zadanko brzmi tak (wiem, że bez testów to nie to samo):

Napisać program, który dla danego grafu wylicza minimalny i maksymalny stopień grafu,
oblicza liczbę składowych spójności grafu oraz odpowiada na pytanie czy graf jest dwudzielny.
Wejście

Liczba wierzchołków, liczba krawędzi i pary liczb mówiące o tym, które wierzchoóki są sąsiadujące.
Wyjście

Liczba będąca minimalnym stopniem grafu, liczba będąca maksymalnym stopniem grafu,
liczba składowych spójności, T-jeśli graf jest dwudzielny/N-jeśli graf nie jest dwudzielny.
Przykład:

Wejście:
4 4
1 2
2 3
3 1
3 4
Wyjście:
1 3 1 N

Wejście:
4 2
1 2
3 4
Wyjście:
1 1 2 T

Uwaga:

Krawędzie mogą być wielokrotne (wtedy wielokrotnie je liczymy). W danych testowych nie ma pętli (krawędzi do tego samego wierzchołka).

Poprawiło mi to trochę szybkość (jeśli zakomentuję sprawdzanie dwudzielności lub spójności wyrzuca mi błędną odpowiedź, wcześniej pomimo zakomentowania jednego z nich miałem i tak przekroczenie), ale wciąż nie mieszczę się w czasie. Coś tu można zrobić jeszcze wydajniej?

Zmień najpierw reprezentację to zobaczymy. Tu masz opis:
http://algorytmika.wikidot.com/wczytywanie
Ja zacznę się wczytywać w Twój kod :).
Edit1:
Możesz też reprezentację grafu jako zmienną globalną, nie będziesz musiał jej przekazywać do funkcji.
Edit2:
Swoją drogą nie robisz BFS'a tylko rekurencyjnego DFS'a. W BFS'ie powinna być kolejka. Jak zmienisz reprezentację grafu to Ci będę mógł to zmienić.
Edit3:
Wydaje mi się, że nie powinno być:

cout << endl;

Jest to zaraz po wczytaniu.
Edit4:
Widzę, że sprawdzanie czy jest dwudzielny też masz rekurencyjnie. Można zrobić to w ten sposób:
BFS i pokolorować na zmianę wierzchołki i potem dla każdego wierzchołka sprawdzić czy jego sąsiedzi są innego koloru niż on. Jeżeli tak to znaczy, że jest dwudzielny.

Zmieniłem to zanim napisałeś ten post :) Mam to identycznie, tyle, że zamiast statycznej tablicy wektorów mam wektor wektorów, w końcu liczba krawędzi nie jest podana, a może być różna w zależności od tego co poda na wejście użytkownik

#include <cstdlib>
#include <iostream>
#include <vector>
#include <list>

using namespace std;

class Node {
  int nr;

  public :
    Node(int nr) {
      this->nr = nr;
    }
    int & GetNr() {
      return nr;
    }
};

//funkcja wypisuje minimalny i maksymalny stopień grafu
void PrintMinAndMax(vector <vector<Node> > graf) {
  int max = graf[0].size(), min = max;
  for (int i = 1; i < graf.size(); ++i) {
    if (graf[i].size() > max) max=graf[i].size();
    if (graf[i].size() < min) min=graf[i].size();
  }
  cout << min << " " << max << " ";
}

// funkcja sprawdza dwudzielność grafu, parametrami są graf w postaci wektora list
// aktualnie przetwarzany wierzchołek (powinno się zaczynać od 0), wektor stanu wierzchołków,
// oraz nr. zbioru do którego ma należeć wierzchołek (kolor wierzchołka)
bool CheckBipartite(vector <vector<Node> > graf, int wierzcholek, vector <int> &wierzcholki, int zbior) {
  bool isBipartite = false;

  for (vector<Node>::iterator current = graf[wierzcholek].begin(); current != graf[wierzcholek].end();) {
    int currentNr = wierzcholki[current->GetNr()];
    if (currentNr == -zbior) {
      ++current;
      continue; //jesli prawidlowo pokolorowany, pomiń
    }
    if (currentNr == zbior) {
      return isBipartite;
    } else {
      wierzcholki[current->GetNr()] = -zbior;
       if (!CheckBipartite(graf, current->GetNr(), wierzcholki, -zbior)) return isBipartite;
    }
    ++current;
  }
  isBipartite = true;
  return isBipartite;
}

void SetVertexAsVisited(vector <vector<Node> > graf, int wierzcholek, vector <int> &wierzcholki) {
  if (wierzcholki[wierzcholek] == 0) {
    wierzcholki[wierzcholek] = 1;
    for (vector<Node>::iterator current = graf[wierzcholek].begin(); current != graf[wierzcholek].end();) {
      SetVertexAsVisited(graf, current->GetNr(), wierzcholki);
      ++current;
    }
  }
}

int HowManyCComponents(vector <vector<Node> > graf, vector <int> &wierzcholki) {
  int ConnectedComponents = 1;
  SetVertexAsVisited(graf, 0, wierzcholki); //najpierw dla 1 wierzcholka
  for (int i=0; i<wierzcholki.size(); ++i) { //maksymalna ilosc skladowych to size()
    if (wierzcholki[i] == 0) {
      ++ConnectedComponents;
      SetVertexAsVisited(graf, i, wierzcholki);
    }
  }
  return ConnectedComponents;
}

int main(int argc, char** argv) {

  int wierzcholki, krawedzie;
  int para1, para2;
  bool isError = false;

  cin >> wierzcholki >> krawedzie;
  vector <vector<Node> > graf(wierzcholki);
  for (int i=0; i < krawedzie; ++i) {
    cin >> para1 >> para2;
    --para1; //wierzcholki numerowane od 1 do size()!
    --para2; //każda operacja wyswietlenia wierzchołków na ekranie
             //musi byc poprzedzona dodaniem jedynki

    if (para1 > wierzcholki || para2 > wierzcholki) {
      isError = true;
      break;
    }
    Node a(para2);
    Node b(para1);
    graf[para1].push_back(a);
    graf[para2].push_back(b);
  }
  cout << endl;
  if (isError) return (EXIT_FAILURE);

  //przypadek szczegolny, graf pusty, badz złożony z samych punktów
  //zawsze jest dwudzielny, max i min stopień grafu = 0, składowe spojności = wierzchołki
  if (krawedzie == 0) {
    cout << "0 0 " << wierzcholki << " T";
    return (EXIT_SUCCESS);
  }

  PrintMinAndMax(graf);

  vector <int> vwierzcholki(wierzcholki); //przetrzymuje stan wierzcholkow
  //do sprawdzenia spójności grafu
  //cout << HowManyCComponents(graf, vwierzcholki) << " ";
  
  //zerowanie wektora stanów
  vwierzcholki.assign(wierzcholki, 0);

  // do sprawdzenia dwudzielności grafu
  vwierzcholki[0] = 1; //nr zbioru pierwszego wierzcholka
  
  if (CheckBipartite(graf, 0, vwierzcholki, 1)) cout << "T";
  else cout << "N\n";
  return (EXIT_SUCCESS);
}

Globalnych się generalnie nie zaleca, więc wolałbym ich nie używać. Ma to jakiś wpływ na szybkość, wielokrotne przekazywanie tego samego parametru?

BFS z kolejką mógłby pomóc? Spróbuję. Co do endl;a, fakt, zapomniałem tego wyrzucić, ale to nie ma wpływu, spoj ignoruje whitespace'y.

Mam też taką myśl, tylko nie wiem czy dałoby się to zrealizować. W obu funkcjach przechodzę przez każdy wierzchołek, może dałoby się je połączyć w jedną i wyeliminować jedno przejście? Możliwe jest to do zrealizowania?

#include <cstdlib>
#include <iostream>
#include <vector>
#include <list>
#include <queue>

using namespace std;

vector <vector<int> > graf;
int wierzcholki, krawedzie;
//funkcja wypisuje minimalny i maksymalny stopień grafu
void PrintMinAndMax() {
  int min,max;
  min=max=graf[0].size();
  for (int i = 1; i < graf.size(); ++i) {
    if (graf[i].size() > max) max=graf[i].size();
    if (graf[i].size() < min) min=graf[i].size();
  }
  cout << min << " " << max << " ";
}

// Dwudzielnosc i liczba spojnych skladowych
void BFS() {
    int Color[wierzcholki]; // 0 - nieodwiedzony, 1 - pierwszy zbior, 2 - drugi zbior
    for(int i=0;i<wierzcholki;++i) Color[i]=0;
      queue<int> Q;
      int V,CC=0;
  for(int i=0;i<wierzcholki;++i)
  {
      if(Color[i]==0)
      {
            ++CC;//zwiekszamy liczbe spojnych skladowych
            Q.push(i);
            Color[i]=1;//kolorujemy go jakos
            while(!Q.empty())
            {
                V=Q.front();
                Q.pop();
                for(int j=0;j<graf[V].size();++j)
                {
                    if(Color[graf[V][j]] == 0)
                    {
                        Color[graf[V][j]]=(Color[V] == 1 ? 2 : 1);//wszyscy sasiedzi sa srugiego koloru
                        Q.push(graf[V][j]);
                    }
                }
            }
      }
  }
  cout << CC << " ";
  for(int i=0;i<wierzcholki;++i)
  {
      for(int j=0;j<graf[i].size();++j)
      {
          if(Color[i]==Color[graf[i][j]])
          {
              cout << "N\n";
              return;
          }
      }
  }
  cout << "T\n";
}

int main(int argc, char** argv) {
    ios_base::sync_with_stdio(0);

  int para1, para2;

  cin >> wierzcholki >> krawedzie;
  graf.resize(wierzcholki);
  for (int i=0; i < krawedzie; ++i) {
    cin >> para1 >> para2;
    --para1; //wierzcholki numerowane od 1 do size()!
    --para2; //każda operacja wyswietlenia wierzchołków na ekranie
             //musi byc poprzedzona dodaniem jedynki
    graf[para1].push_back(para2);
    graf[para2].push_back(para1);
  }

  //przypadek szczegolny, graf pusty, badz złożony z samych punktów
  //zawsze jest dwudzielny, max i min stopień grafu = 0, składowe spojności = wierzchołki
  if (krawedzie == 0) {
    cout << "0 0 " << wierzcholki << " T";
    return (EXIT_SUCCESS);
  }

  PrintMinAndMax();
  BFS();
  return (EXIT_SUCCESS);
}

Sprawdź czy działa :). Ogólnie jak są zadania algorytmiczne itp. to warto stosować zmienne globalne, gdyż przekazywanie przez funkcje wiąże ze sobą konieczność kopiowania(funkcje nie operują na oryginale tylko kopi).
Tutaj właśnie przechodzę raz graf. Wartość 0 dla wierzchołka oznacza, że był nie odwiedzony. Potem może mieć kolor 1 lub 2. Są one przyznawane na zmianę(tak jakby poziomami drzewa BFS). Potem jest sprawdzenie czy każdy wierzchołem ma sąsiadów innego koloru.

Działa, dzięki dobry człowieku, niech Ci Bozia w dzieciach wynagrodzi. ;)