차수 수열 그래프 구성

Time Limit: 3000 msMemory Limit: 256 MBDiamond V8Author: Super Admin그래프구성적

문제

$N$ 개의 정수로 이루어진 차수 수열이 주어진다. 이 차수 수열을 갖는 단순 그래프(무방향 그래프이며, 자기 간선과 다중 간선이 없는 그래프)를 구성하라. 구성이 불가능하다면 -1을 출력하라.

차수 수열이 단순 그래프로 구성 가능한지 판별하기 위해 Erdős-Gallai 정리를 활용하라. Erdős-Gallai 정리에 따르면, 차수 수열을 내림차순으로 정렬한 $d_1 \ge d_2 \ge \dots \ge d_N$ 에 대해 모든 ()에 대하여 다음 부등식을 만족하는 경우에만 단순 그래프로 구성할 수 있다.

Problem Statistics

Total submissions

Accepted

29.4%

Acceptance rate

Unique solvers

Similar Problems

502보물섬 탐험
Gold V5
336작업 순서
Gold III6
654신호망 재구성
Silver III4
303그래프 경로 존재 여부
Silver III4
334

≥

⋯≥

k

1 \le k \le N

$\sum_{i=1}^{k} d_i \le k(k-1) + \sum_{i=k+1}^{N} \min(d_i, k)$

입력

첫째 줄에 정점의 수 $N$ 이 주어진다.
둘째 줄에 각 정점의 차수를 나타내는 $N$ 개의 정수가 공백으로 구분되어 주어진다.

$1 \le N \le 1,000$
$0 \le d_i \le N-1$

출력

주어진 차수 수열로 단순 그래프를 구성할 수 있다면, 첫째 줄에 간선의 수 $M$ 을 출력한다. 둘째 줄부터 $M$ 개의 줄에 걸쳐 각 간선의 양 끝 정점 번호 $u$ 와 $v$ 를 공백으로 구분하여 출력한다. 간선의 출력 순서와 정점의 출력 순서는 상관없다. 모든 정점의 차수가 0이어서 간선이 하나도 없는 경우, 첫째 줄에 0만 출력한다.

그래프를 구성할 수 없다면 첫째 줄에 -1을 출력한다.

예제 입력 1

4
3 3 3 3

예제 출력 1

예제 입력 2

3
3 2 1

예제 출력 2

-1

위상 정렬

Gold V5