Graf spójny nieskierowany

Witam,
mam za zadanie wylosować spójny graf nieskierowany (reprezentacja grafu to lista sąsiedztwa) o N wierzchołkach i parzystym stopniu każdego z wierzchołków, o współczynniku nasycenia krawędziami 50%. Kod wygląda tak:

 
nasycenie = ((N*(N-1))/2)*0.5;

        for(i=0; i < nasycenie; i++)
        {
                a = rand()%N;
                b = rand()%N;
                push_back(L1[a], b); //push_back - dodawanie na koniec listy 
               if(a !=b) push_back(L1[b], a);
        }

Problem w tym, że kod tworzy te grafy, ale nie zawsze są spójne, jak to zrobić by były ?

Losuj tyle aż będzie spójny.

Chodzi o to żeby zawsze był spójny

Dziwne pytanie. losuj zawsze 1 wierzchołek który już jest w grafie. Wtedy zawsze będzie spójny.

Może uściślę co napisał @Shalom

1. Losujesz jeden wierzchołek, i zaznaczasz że należy on do grafu, reszta jeszcze nie należy do grafu
2. Jeżeli brak wierzchołków nie należących do grafu to koniec
3. Losujesz jeden wierzchołek z tych należących do grafu drugi zaś losujesz z tych nie należących do grafu
4. Łączysz wylosowane wierzchołki i zaznaczasz ten drugi że już należy do grafu
5. Przechodzisz do punktu 2.

nasycenie=(0.5*0.5)*N*(N-1);
if(nasycenie<N-1) nasycenie=N-1;
for(i=1;i<=nasycenie;++i)
  {
   if(i<N)
     {
      a=rand()%i;
      b=i; 
     }
   else
     {
      a=rand()%N;
      b=rand()%(N-1);
      b+=(b>=a);
     }
   push_back(L1[a],b);
   push_back(L1[b],a);
  }

Generuj dowolną macierz górno/dolnotrójkątną z zadanym nasyceniem i potem dajesz sumę z transpozycją (by był nieskierowany).

Dzięki _13th_Dragon pięknie śmiga :)