Reachable Pairs

题目描述

考虑一张无向图，有 $N$ 个点，编号为 $1\dots N$，以及 $M$ 条边 （$1\le N\le 2\cdot 10^5, 0\le M\le 4\cdot 10^5$）。给定一个二进制字符串 $s_1s_2\dots s_N$。在时刻 $t$（对每个 $t\in [1,N]$）， 如果 $s_t=0$，则点 $t$ 从图中被删除。 如果 $s_t=1$，则点 $t$ 从图中被删除，并且在删除之前，向点 $t$ 的所有邻居两两之间添加边。 注意：在两种情况下，当一个点从图中删除时，与它相连的所有边也都会被删除。 请统计在每个时刻 $1\ldots N$ 之前（即执行该时刻的删除操作之前），有多少对点可以通过某条边序列互相到达。

输入格式

第一行包含 $N$ 和 $M$。 第二行包含长度为 $N$ 的比特串 $s$。 接下来 $M$ 行每行包含两个整数，表示图中的一条边。

输出格式

输出 $N$ 行，分别表示每个时刻之前的可互相到达的点对数量。

3 2
111
1 2
1 3

3
1
0

3 2
000
1 2
1 3

3
0
0

7 8
1101101
6 2
1 2
2 3
6 3
1 3
1 7
4 5
2 7

11
7
4
2
1
1
0

提示

在进行任何删除之前，所有点对都可以互相到达。删除点 $1$ 后，会在 $2$ 与 $3$ 之间添加一条边，因此它们仍然可以互相到达。 在进行任何删除之前，所有点对都可以互相到达。删除点 $1$ 后，$2$ 与 $3$ 不再能互相到达。

计分： 输入 4-6：$N\le 100$ 输入 7-8：所有 $s_i$ 均为 0。 输入 9-11：所有 $s_i$ 均为 1。 输入 12-23：无额外限制。 题目贡献：Benjamin Qi

标签: USACO|2025|Gold

来源

USACO|2025|Gold