Come rimuovo un arco da un grafo?

Stavo vedendo il problema (marathon CMSocial - a social coding app) e la mia idea per quanto riguarda la parte dell’evento 1 in cui la strada si apre se chiusa o si chiude se aperta, era di avere un vector< int > adj[MAXN] in cui metto gli archi e nel caso in cui una strada si chiude la elimino dalla lista di adiacenza, ora il problema è questo, come faccio ad eliminare un arco? Cercando su google ho trovato il .erase(inizio, fine) e il .clear (che non va bene in questo caso).

Ho provato a fare questo ciclo per verificare se il collegamento esiste già perchè solo in quel caso deve rimuoverlo altrimenti deve aggiungerlo e per quello non è un problema

for(int u=0;u<adj[x].size();u++){
        if(adj[x][u]==y){
        	adj[x].erase(u,u);	
        }

Dovrebbe cercare tra tutti i collegamenti del nodo x il nodo y, e se lo trova deve eliminare il collegamento ma mi da errore, come posso fare? (il for che ho messo è solo per eliminare la strada ma manca un break ed un controllo per aggiungere la strada se non esiste già, ma quello non è un problema)

In generale quando vuoi eliminare archi da grafi hai queste opzioni:

  • se devi eliminare un arco mentre stai scorrendo fai swap con l’ultimo elemento e pop_back
  • se il prob e’ piccolo usi una matrice di adiacenza
  • se devi eliminare poche volte e ti va bene lineare puoi fare find e erase
  • usi set/map per le liste di adiacenza

In particolare in questo problema, essendo il grafo un albero, ogni arco e’ univocamente identificato dal figlio, quindi sarebbe molto piu semplice markarlo come eliminato, ma in ogni caso in questo problema anche se sai se un arco c’e’ o no facilmente, non e’ banale rispondere alle query, per risolvere 100/100 bisogna(?) tenere l’albero in qualche struttura diversa.

Richiesta di spoiler: serve la hld?

puoi usarlo, ma puoi fare di meglio

Il tempo migliore io l’ho fatto con hld, ma sono sicuro che tu sarai pronto a smentirmi :face_with_raised_eyebrow:

Io ci ho pensato poco a sto problema quindi boh ma mi e’ stato detto che si puo fare con euler tour order