题目详情题解（0）讨论（0）提交记录（0）

AT_abc229_e.[ABC229E] Graph Destruction

普及+/提高

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个包含 NN 个顶点、MM 条边的简单无向图。
第 ii 条边连接顶点 AiA_i 和 BiB_i。

现在依次删除顶点 1,2,…,N1,2,\ldots,N。
删除顶点 ii 意味着将顶点 ii 以及与顶点 ii 相连的所有边从图中移除。

对于每个 i=1,2,…,Ni=1,2,\ldots,N，请输出删除到顶点 ii 时，图中连通分量的数量。

输入格式

输入以以下格式从标准输入读入。

NN MM
A1A_1 B1B_1
A2A_2 B2B_2
⋮\vdots
AMA_M BMB_M

输出格式

输出 NN 行。
第 ii 行输出删除到顶点 ii 时，图中连通分量的数量。

输入输出样例

  • 输入#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

    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≤N≤2×1051 \leq N \leq 2 \times 10^5
  • 0≤M≤min⁡(N(N−1)2, 2×105)0 \leq M \leq \min\left(\frac{N(N-1)}{2},\ 2 \times 10^5\right)
  • 1≤Ai<Bi≤N1 \leq A_i < B_i \leq N
  • 若 i≠ji \neq j，则 (Ai,Bi)≠(Aj,Bj)(A_i,B_i) \neq (A_j,B_j)
  • 所有输入均为整数

样例解释 1


图会如上图所示逐步变化。

样例解释 2

初始时图也可能是不连通的。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页