Problem
Existem n vértices em um grafo não direcionado, mas ele não possui arestas. arestas m são gradualmente adicionadas ao gráfico.
Após cada adição de uma aresta, você precisa descobrir o número de componentes conectados.
Um grafo pode ter loops e múltiplas arestas.
Entrada:
A primeira linha contém dois números - n e m (1 <= n <= 300000, 0 <= m <= 500000) - o número de vértices do gráfico e o número de arestas adicionadas.
As próximas m linhas contêm dois números u, v (1 <= u, v <= n) - eles significam que uma aresta (u, v) foi adicionada ao gráfico.
Saída:
Após cada adição de uma aresta, imprima o número de componentes conectados do grafo.
|
Entrar |
Saída |
|
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