Problem
Es gibt n Eckpunkte eines nicht ausgerichteten Graphen, es gibt keine Kanten darin. Dem Diagramm werden nach und nach m Kanten hinzugefügt.
Nach jedem Hinzufügen einer Kante müssen Sie die Anzahl der Konnektivitätskomponenten ermitteln.
Es kann Schleifen und vielfache Kanten in einem Diagramm geben.
Eingabe:
In der ersten Zeile sind die beiden Zahlen n und m (1 <= n <= 300.000, 0 <= m <= 500.000) die Anzahl der Scheitelpunkte des Graphen und die Anzahl der hinzuzufügenden Kanten.
In den folgenden m-Zeilen haben zwei Zahlen u, v (1 <= u, v <= n) - sie bedeuten, dass eine Kante (u, v) zum Diagramm hinzugefügt wurde.
Ausgabe:
Geben Sie nach jedem Hinzufügen einer Kante die Anzahl der Konnektivitätskomponenten des Diagramms aus.
|
Eingabe |
Ausgabe |
|
3 2
1 2
2 3
|
2
1 |
|
3 6
1 1
2 2
3 3
1 1
2 2
1 2
|
3
3
3
3
3
2
|
(c) Ibrahim Ahmad, 2018