AT_abc229_e [ABC229E] Graph Destruction
题目描述
给定一个包含 $N$ 个顶点、$M$ 条边的简单无向图。
第 $i$ 条边连接顶点 $A_i$ 和 $B_i$。
现在依次删除顶点 $1,2,\ldots,N$。
删除顶点 $i$ 意味着将顶点 $i$ 以及与顶点 $i$ 相连的所有边从图中移除。
对于每个 $i=1,2,\ldots,N$，请输出删除到顶点 $i$ 时，图中连通分量的数量。
输入格式
输入以以下格式从标准输入读入。
> $N$ $M$
> $A_1$ $B_1$
> $A_2$ $B_2$
> $\vdots$
> $A_M$ $B_M$
输出格式
输出 $N$ 行。
第 $i$ 行输出删除到顶点 $i$ 时，图中连通分量的数量。
说明/提示
## 限制条件
- $1 \leq N \leq 2 \times 10^5$
- $0 \leq M \leq \min\left(\frac{N(N-1)}{2},\ 2 \times 10^5\right)$
- $1 \leq A_i < B_i \leq N$
- 若 $i \neq j$，则 $(A_i,B_i) \neq (A_j,B_j)$
- 所有输入均为整数
## 样例解释 1
图会如上图所示逐步变化。
## 样例解释 2
初始时图也可能是不连通的。
由 ChatGPT 4.1 翻译