Problem
Hay n vértices en un gráfico no dirigido, pero no tiene bordes. Los bordes m se agregan gradualmente al gráfico.
Después de cada adición de un borde, debe averiguar la cantidad de componentes conectados.
Un gráfico puede tener bucles y múltiples aristas.
Entrada:
La primera línea contiene dos números - n y m (1 <= n <= 300000, 0 <= m <= 500000) - el número de vértices del gráfico y el número de aristas añadidas.
Las siguientes m líneas contienen dos números u, v (1 <= u, v <= n) - significan que se ha agregado un borde (u, v) al gráfico.
Salida:
Después de cada adición de un borde, imprime el número de componentes conectados del gráfico.
|
Entrar |
Salida |
|
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