Reachable Pairs
플래티넘 II의견: 0
Consider an undirected graph with \(N\) nodes labeled \(1\dots N\) and \(M\) edges
(\(1\le N\le 2\cdot 10^5, 0\le M\le 4\cdot 10^5\)). You're given a binary string
\(s_1s_2\dots s_N\). At time \(t\) for each \(t\in [1,N]\),
- If \(s_t=0\), node \(t\) is removed from the graph.
- If \(s_t=1\), node \(t\) is removed from the graph, and edges are added between every pair of neighbors that node \(t\) had just before removal.
Note that in both cases, when a node is removed from the graph all of its
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\ldots N\).
Problem credits: Benjamin Qi
SCORING
- Inputs 4-6: \(N\le 100\)
- Inputs 7-8: All \(s_i\) equal zero.
- Inputs 9-11: All \(s_i\) equal one.
- Inputs 12-23: No additional constraints.
Problem credits: Benjamin Qi
The first line contains \(N\) and \(M\).
The second line contains the bit string \(s\) of length \(N\).
The next \(M\) lines each contain two integers denoting an edge of the graph.
\(N\) lines, the number of pairs before each timestep.
3 2
111
1 2
1 33
1
0Before 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.
3 2
000
1 2
1 33
0
0Before 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.
7 8
1101101
6 2
1 2
2 3
6 3
1 3
1 7
4 5
2 711
7
4
2
1
1
0평가 및 의견
Reachable Pairs
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Reachable Pairs