#PU1474. USACO 2025 January Contest, Gold — Problem 2. Reachable Pairs

    ID: 1561 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高+/省选- 上传者: 标签>USACO赛事:jan25来源:usaco.orgscoring:equal_test_cases并查集字符串

USACO 2025 January Contest, Gold — Problem 2. Reachable Pairs

USACO 2025 January Contest, Gold — Problem 2. Reachable Pairs

题目描述

Consider an undirected graph with NN nodes labeled 1…N1\dots N and MM edges (1≤N≤2⋅105,0≤M≤4⋅1051\le N\le 2\cdot 10^5, 0\le M\le 4\cdot 10^5). You're given a binary string s1s2…sNs_1s_2\dots s_N. At time tt for each t∈[1,N]t\in [1,N], If st=0s_t=0, node tt is removed from the graph. If st=1s_t=1, node tt is removed from the graph, and edges are added between every pair of neighbors that node tt had just before removal.

输入格式

The first line contains NN and MM. The second line contains the bit string ss of length NN. The next MM lines each contain two integers denoting an edge of the graph.

输出格式

NN lines, the number of pairs before each timestep.

数据范围

Inputs 4-6: N≤100N\le 100 Inputs 7-8: All sis_i equal zero. Inputs 9-11: All sis_i equal one. Inputs 12-23: No additional Problem credits: Benjamin Qi

样例

样例 1

3 2
111
1 2
1 3
3
1
0
Before any removals, all pairs of nodes are reachable from each other. After
node $1$ is removed, an edge is added between $2$ and $3$, so they can still
reach each other.

样例 2

3 2
000
1 2
1 3
3
0
0
Before any removals, all pairs of nodes are reachable from each other. After
node $1$ is removed, $2$ and $3$ can no longer reach each other.

样例 3

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

提示

incident edges are removed as well. Count the number of pairs of nodes that can reach each other via some sequence of edges just before each of timesteps 1…N1\ldots N.