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

输入 #1

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

输出 #1

1
2
3
2
1
0

输入输出样例 #2

输入 #2

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

输出 #2

3
2
2
1
1
1
1
0

说明/提示

限制条件

• $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 翻译