Problem
Ci sono n vertici in un grafo non orientato, ma non ha spigoli. m spigoli vengono aggiunti gradualmente al grafico.
Dopo ogni aggiunta di un bordo, devi scoprire il numero di componenti collegati.
Un grafico può avere loop e più spigoli.
Inserimento:
La prima riga contiene due numeri - n e m (1 <= n <= 300000, 0 <= m <= 500000) - il numero di vertici del grafico e il numero di spigoli aggiunti.
Le m righe successive contengono due numeri u, v (1 <= u, v <= n) - indicano che è stato aggiunto un arco (u, v) al grafico.
Risultato:
Dopo ogni aggiunta di un arco, stampa il numero di componenti connesse del grafico.
|
Entra |
Uscita |
|
3 2
1 2
2 3
|
2
1 |
|
36
1 1
2 2
3 3
1 1
2 2
1 2
|
3
3
3
3
3
2
|
(c) Ibrahim Ahmad, 2018