Graph Construction

$i$번 정점에서 번호가 더 큰 정점으로 이어지는 간선의 수를 $R_i$, 번호가 더 작은 정점으로 이어지는 간선의 수를 $L_i$라고 하자. 그러면 $L_i+R_i=D_i$이다.

$X_0=0$, $L_0=0$으로 두자. $X_{i-}$에서 로 넘어갈 때 왼쪽 끝점이 인 간선 개가 새로 포함되고, 오른쪽 끝점이 인 간선 개가 제외된다. 따라서 이고, 다음 식으로 를 앞에서부터 유일하게 복원할 수 있다.

$$R_i=X_i-X_{i-1}+L_{i-1},\qquad L_i=D_i-R_i.$$

각 $i$에 대해 $0\le R_i\le N-i$, $0\le L_i\le i-1$이어야 한다. 하나라도 만족하지 않으면 을 출력한다.

이제 정점을 $1$부터 $N$까지 순서대로 처리한다. 이전에 처리한 각 정점에 대해 앞으로 번호가 더 큰 정점과 연결해야 하는 남은 간선 수를 저장한다. $i$번 정점을 처리할 때는 이전 정점 중 정확히 $L_i$개를 골라 $i$번 정점과 연결해야 한다.

남은 간선 수가 가장 큰 $L_i$개의 정점을 고른다. 우선순위 큐에 $(\text{남은 간선 수},\text{정점 번호})$를 저장한다. 가장 큰 원소를 $L_i$개 꺼내 정점 번호 를 얻을 때마다 간선 를 답에 추가하고 남은 간선 수를 감소시킨 뒤 다시 넣는다. 마지막으로 를 넣는다. 필요한 정점 수가 부족하거나 꺼낸 최댓값이 이면 불가능하다. 모든 정점을 처리한 뒤 남은 값이 모두 인지도 확인한다.

끝까지 성공했다면 기록한 간선들이 조건을 만족하는 그래프이므로 간선 개수와 간선 목록을 출력한다.

증명

어떤 가능한 그래프에서 현재 정점 $i$가 이전 정점 $y$와 연결되어 있고, 이전 정점 $x$와는 연결되어 있지 않다고 하자. 현재 남은 간선 수가 $r_x\ge r_y$라고 하자.

출력할 간선의 수를 $M$이라 하자. 우선순위 큐 연산 횟수는 $O(N+M)$이므로 시간 복잡도는 $O(N^2\log N)$이다. 구성한 간선을 저장하기 위해 의 공간을 사용할 수 있다.