#PU1474. USACO 2025 January Contest, Gold — Problem 2. Reachable Pairs
USACO 2025 January Contest, Gold — Problem 2. Reachable Pairs
USACO 2025 January Contest, Gold — Problem 2. Reachable Pairs
题目描述
Consider an undirected graph with nodes labeled and edges (). You're given a binary string . At time for each , If , node is removed from the graph. If , node is removed from the graph, and edges are added between every pair of neighbors that node had just before removal.
输入格式
The first line contains and . The second line contains the bit string of length . The next lines each contain two integers denoting an edge of the graph.
输出格式
lines, the number of pairs before each timestep.
数据范围
Inputs 4-6: Inputs 7-8: All equal zero. Inputs 9-11: All 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 .