[R31D]连通块 - 代码源竞赛平台

时空限制

1S/512M

题目描述

给定一个包含 $n$ 个顶点（编号 $1$ 到 $n$）和 $m$ 条边的无向图。

你需要依次回答 $n$ 个独立的询问。对于每个询问 $i$ ($1 \le i \le n$)，请计算：

• 从原图中临时移除所有满足 $u \le i < v$ 的边 $(u, v)$。

• 统计剩余图的连通块数量。

注意：每个询问开始时，图都会恢复为初始状态。

格式

输入格式

第一行包含两个整数 $n$ 和 $m$，分别表示图的顶点数和边数。

接下来 $m$ 行，每行包含两个整数 $u$ 和 $v$，表示顶点 $u$ 和顶点 $v$ 之间存在一条无向边。

输出格式

输出一行，包含 $n$ 个用空格分隔的整数。第 $k$ 个整数表示当 $i=k$ 时，图中连通块的数量。

样例

样例输入 #1

5 5
1 2
2 3
3 4
4 5
1 5

样例输出 #1

2 2 2 2 1

样例解释 #1

• 当 $i = 1$ 时:

  • 边 $(1, 2)$，$(1, 5)$ 被移除。形成的连通块为 $\{1 \}$ 和 $\{2, 3, 4, 5\}$，共 $2$ 个。

• 当 $i = 2$ 时:

  • 边 $(2, 3)$，$(1, 5)$ 被移除。形成的连通块为 $\{1, 2\}$ 和 $\{3, 4, 5\}$，共 $2$ 个。

• 当 $i = 3$ 时:

  • 边 $(3, 4)$，$(1, 5)$ 被移除。形成的连通块为 $\{1, 2, 3\}$ 和 $\{4, 5\}$，共 $2$ 个。

• 当 $i = 4$ 时：

  • 边 $(4, 5)$，$(1, 5)$ 移除。 形成的连通块为 $\{1, 2, 3, 4\}$ 和 $\{5\}$，共 $2$ 个。

• 当 $i = 5$ 时:

  • 没有边被移除。图是连通的，连通块数量为 $1$。

数据规模

对于 $40\%$ 的数据， $1 \leq n, m \leq 2000$。

对于 $100\%$ 的数据， $1 \leq n, m \leq 2 \times 10^5$，$1 \leq u < v \leq n$。