페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8262

접근가능쌍 1초 1024MB

문제

무방향 그래프가 N (1 \leq N \leq 2 \cdot 10^5) 개의 노드와 M (0 \leq M \leq 4 \cdot 10^5) 개의 간선을 가진다. 노드는 1부터 N까지 번호가 매겨져 있다. 길이 N 인 이진 문자열 s_1s_2 \dots s_N​ 가 주어진다.

각 시간 t (t \in [1, N]) 에 대해 다음 작업을 수행한다.

  • 만약 s_t = 0 이면, 노드 t 를 그래프에서 제거한다.

  • 만약 s_t = 1 이면, 노드 t 를 그래프에서 제거하고, 제거되기 직전의 이웃들 사이에 간선을 추가한다.

각 시간 t 직전에 서로 도달 가능한 노드 쌍의 개수를 출력한다.


입력

첫 번째 줄에 N 과 M 이 주어진다.

두 번째 줄에 길이 N 의 이진 문자열 s 가 주어진다.

다음 M 개의 줄에 각 간선을 나타내는 두 정수 u, v 가 주어진다.


출력

N 개의 줄을 출력하며, 각 줄에 타임스텝 t 직전까지 서로 도달 가능한 노드 쌍의 개수를 출력한다.


부분문제

번호 점수 조건
#120점

N≤100

#215점

모든 s_i는 0이다.

#315점

모든 s_i는 1이다.

#450점

추가 제약 조건 없음


예제1

입력
32
111
12
13
출력
3
1
0

노드가 제거되기 전에는 모든 노드 쌍이 서로 도달 가능하다. 노드 1이 제거된 후, 2와 3 사이에 간선이 추가되므로 여전히 서로 도달할 수 있다.


예제2

입력
32
000
12
13
출력
3
0
0

노드가 제거되기 전에는 모든 노드 쌍이 서로 도달 가능하다. 노드 1이 제거된 후, 2와 3은 더 이상 서로 도달할 수 없다.


예제3

입력
78
1101101
62
12
23
63
13
17
45
27
출력
11
7
4
2
1
1
0

출처

USACO 2025 January Gold

역링크