시간 창의 연결망
다이아몬드 II의견: 0
\(N\)개의 정점이 있고, 처음에는 간선이 하나도 없다. 총 \(Q\)번의 단계가 진행된다. \(i\)번째 단계에서는 두 정점 \(u_i\), \(v_i\)를 잇는 간선 하나가 추가된다.
단, 각 간선의 수명은 정확히 \(K\)단계이다. \(i\)번째 단계에서 추가된 간선은 단계 \(i, i+1, \dots, i+K-1\) 동안만 존재하고, 단계 \(i+K\)가 시작되기 직전에 사라진다 (자기 루프 \(u_i = v_i\) 도 가능하며, 같은 두 정점을 잇는 간선이 여러 개 동시에 존재할 수도 있다).
각 단계 \(i\)를 처리한 직후(즉 \(i\)번째 간선을 추가하고 수명이 다한 간선들을 제거한 뒤), 현재 살아 있는 간선들만 고려했을 때 \(N\)개 정점이 이루는 연결 요소의 개수를 출력해야 한다.
\(1 \le N \le 100{,}000\)
\(1 \le Q \le 100{,}000\)
\(1 \le K \le Q\)
\(1 \le u_i, v_i \le N\)
첫 줄에 단계 수(=간선 수) \(Q\), 정점 수 \(N\), 수명 \(K\)가 주어진다.
이어서 \(Q\)개의 줄에 \(i\)번째 단계에서 추가되는 간선의 두 정점 \(u_i\), \(v_i\)가 주어진다.
각 단계 직후의 연결 요소 개수를 단계 순서대로 한 줄에 하나씩, 총 \(Q\)줄 출력한다.
4 4 2
1 2
2 3
3 4
1 4
3
2
2
2N=4, K=2. 단계1: 간선(1-2) 살아있음 -> 요소 {1,2},{3},{4} = 3. 단계2: (1-2),(2-3) -> {1,2,3},{4} = 2. 단계3: (1-2)는 만료, (2-3),(3-4) -> {1},{2,3,4} = 2. 단계4: (2-3)만료, (3-4),(1-4) -> {1,3,4},{2} = 2.
3 3 3
1 2
2 3
1 1
2
1
1N=3, K=3 이라 모든 간선이 끝까지 살아있다. 단계1: (1-2) -> 2. 단계2: (1-2),(2-3) -> 1. 단계3: 자기루프(1-1) 추가는 연결성 변화 없음 -> 1.
riseoj 작성
출처 Original
평가 및 의견
시간 창의 연결망
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
시간 창의 연결망