스테리 스카이☆퍼레이드

마지막에 추가된 별은 기존 모든 별과 연결되었거나 어느 별과도 연결되지 않았다. 따라서 현재 남아 있는 정점이 $S$개라면 차수가 $S-1$인 정점 또는 차수가 $0$인 정점을 하나 제거할 수 있다. 이를 정점 하나만 남을 때까지 반복하면 정점이 추가된 순서와 각 정점이 추가될 때 사용한 방법을 역순으로 복원할 수 있다.

이 제거 과정을 빠르게 구현해 보자. 처음 그래프에서의 정점 $v$의 차수를 $D_v$라 하고, 지금까지 제거한 연결 정점의 개수를 $C$라 하자. 제거된 연결 정점은 현재 남아 있는 모든 정점과 인접했고, 제거된 고립 정점은 현재 남아 있는 어떤 정점과도 인접하지 않았다. 따라서 아직 남은 정점 $v$의 현재 차수는 항상

$$D_v-C$$

이다.

현재 정점이 $S$개 남았다면 다음 정점을 제거할 수 있다.

• $D_v=C$인 정점은 현재 차수가 $0$인 고립 정점이다.
• $D_v=C+S-1$인 정점은 현재 차수가 인 연결 정점이다.

초기 차수별로 정점을 버킷에 넣으면 매 단계에서 필요한 정점을 $O(1)$에 꺼낼 수 있다. 입력이 조건을 만족하므로 둘 중 하나는 항상 존재한다. 간선을 읽어 초기 차수를 계산하는 시간을 포함하여 복원에는 $O(N+M)$이 걸린다.

이제 제거 기록을 거꾸로 따라가며 밝기를 정한다. 처음 정점의 밝기는

$$\left\lceil\frac N2\right\rceil$$

로 둔다. 지금까지 정한 밝기의 최솟값을 $L$, 최댓값을 $R$이라고 하자.

• 고립 정점을 추가한다면 밝기를 $N-R$로 정한다. 기존 모든 밝기와의 합이 $N$ 이하이므로 새 간선이 생기지 않는다.
• 연결 정점을 추가한다면 밝기를 $N-L+1$로 정한다. 기존 모든 밝기와의 합이 $N$보다 크므로 모든 기존 정점과 연결된다.

마지막으로 모든 밝기가 $1$ 이상 $N$ 이하임을 보이자. 매 단계에서

$$L+R\in\{N,N+1\}$$

가 유지된다. 또한 정점을 하나 추가할 때마다 $R-L$은 최대 $1$ 증가하므로, 전체 과정에서 $R-L\leq N-1$이다. 두 성질을 합치면 $L\geq1$, 을 얻는다.

시간 복잡도는 $O(N+M)$이고 공간 복잡도도 $O(N+M)$이다.

Solution written by GPT6