Graph Destruction

题目描述

给出一个有 $N$ 个顶点和 $M$ 条边的无向图。
边 $i$ 连接顶点 $A_i$ 和 $B_i$。 我们将按顺序擦除顶点 $1, 2, \ldots, N$。
这里，擦除顶点 $i$ 意味着从图中删除顶点 $i$ 以及所有与顶点 $i$ 相邻的边。 对于每个 $i=1, 2, \ldots, N$，当顶点 $1$ 到顶点 $i$ 被删除时，图有多少个连通分量？

输入格式

输入从标准输入按以下格式提供： $N$ $M$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_M$ $B_M$

输出格式

输出 $N$ 行。
第 $i$ 行应包含在顶点 $1$ 到顶点 $i$ 被删除时图的连通分量数。

6 7
1 2
1 4
1 5
2 4
2 3
3 5
3 6

1
2
3
2
1
0

8 7
7 8
3 4
5 6
5 7
5 8
6 7
6 8

3
2
2
1
1
1
1
0

提示

$1 \leq N \leq 2 \times 10^5$ $0 \leq M \leq \min(\frac{N(N-1)}{2} , 2 \times 10^5 )$ $1 \leq A_i \lt B_i \leq N$ $(A_i,B_i) \neq (A_j,B_j)$ if $i \neq j$. 输入中的所有数值均为整数。
上图显示了图的变化过程。
图可能一开始就是不连通的。

标签: AtCoder|abc229E

来源

AtCoder|abc229E