Problem
Il y a n sommets dans un graphe non orienté, mais il n'a pas d'arêtes. m arêtes sont progressivement ajoutées au graphique.
Après chaque ajout d'arête, il faut connaître le nombre de composants connectés.
Un graphique peut avoir des boucles et plusieurs arêtes.
Saisie :
La première ligne contient deux chiffres - n et m (1 <= n <= 300000, 0 <= m <= 500000) - le nombre de sommets du graphe et le nombre d'arêtes ajoutées.
Les m lignes suivantes contiennent deux nombres u, v (1 <= u, v <= n) - ils signifient qu'une arête (u, v) a été ajoutée au graphique.
Sortie :
Après chaque ajout d'une arête, imprimez le nombre de composantes connexes du graphe.
Entrez
Sortie
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