레이팅 미적용\(1\dots N\)으로 번호가 매겨진 노드 \(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\in [1,N]\)에 대해 시각 \(t\)에,
- \(s_t=0\)이면 노드 \(t\)가 그래프에서 제거된다.
- \(s_t=1\)이면 노드 \(t\)가 그래프에서 제거되고, 제거 직전에 노드 \(t\)가 가지고 있던 이웃들의 모든 쌍 사이에 간선이 추가된다.
두 경우 모두, 노드가 그래프에서 제거될 때 그 노드에 연결된 모든 간선도 함께 제거된다는 점에 유의하라.
각 시각 \(1\ldots N\) 직전에, 어떤 간선 열을 통해 서로 도달할 수 있는 노드 쌍의 수를 세시오.
Problem credits: Benjamin Qi
배점
- 입력 4-6: \(N\le 100\)
- 입력 7-8: 모든 \(s_i\)가 0이다.
- 입력 9-11: 모든 \(s_i\)가 1이다.
- 입력 12-23: 추가 제약이 없다.
Problem credits: Benjamin Qi
첫째 줄에 \(N\)과 \(M\)이 주어진다.
둘째 줄에 길이 \(N\)의 비트 문자열 \(s\)가 주어진다.
다음 \(M\)개의 줄에 각각 그래프의 간선을 나타내는 두 정수가 주어진다.
각 시각 직전의 쌍의 수를 \(N\)개의 줄에 출력한다.
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