Stiu ca se poate, si cum se poate. Problema e ca fiind arhiva educationala omu vine si invata problema se uita si peste sursa oficiala, face stergerea in O(N) ia 100 la problema si zice "da dom'le stiu sa rezolv problema". Apoi se duce la concurs implementeaza aceeasi solutie si ia 50 de puncte pe teste mai bune si se intreaba "de ce?". Asta e singurul lucru pe care vroiam sa-l punctez.

Ce te face sa presupui ca muchiile sunt distribuite uniform? Vorbim de analiza in cazul cel mai defavorabil nu in cazul mediu. Considera graful urmator: N noduri (N par) 1 si 2 noduri speciale 1 are muchie catre toate cele N-2 noduri ramase, 2 la fel (in total 2*(N-2) muchii deci graf deloc dens) cati vecini are 1 si cat dureaza sa elimini un element din lista lui de vecini?

Testele sunt slabe si nu diferentiaza o astfel de solutie de una optima.

Cod:

void sterge( int v, int w ) 
{
  deg[v]--, deg[w]--;
  G[v].pop_front();
  TR( G[w], it )
   if( *it == v ) 
   {
       G[w].erase( it );
       break;
   }
}

Mi se pare destul de O(n)  . Un varf poate sa aiba N vecini si ala pe care il stergi sa fie ultimul in lista.

Solutia prezentata ca fiind optima e O(M*N), eliminarea unei muchii se face in O(N) deci nu intra in timp pe niste teste bune.