Problem
無向グラフには n 個の頂点がありますが、エッジはありません。 m 個のエッジが徐々にグラフに追加されます。
エッジを追加するたびに、接続されたコンポーネントの数を調べる必要があります。
グラフには、ループと複数のエッジを含めることができます。
入力:
最初の行には 2 つの数字が含まれています - n と m (1 <= n <= 300000, 0 <= m <= 500000) - グラフの頂点の数と追加されたエッジの数。
次の m 行には、2 つの数値 u、v (1 <= u、v <= n) が含まれています。これは、エッジ (u, v) がグラフに追加されたことを意味します。
出力:
エッジを追加するたびに、グラフの連結成分の数を出力してください。
<本体>
|
入る |
出力 |
|
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) イブラヒム・アフマド、2018年